Submission #2966055
Source Code Expand
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;
struct LCA{
int n,h;
vector<vector<int>> v,par;
vector<int> depth,ord;
LCA(int sz):n(sz),v(n),depth(n),ord(n){
h=1;
while(h<=n)h*=2;
par.assign(h,vector<int>(n,-1));
}
void add_edge(int x,int y){
v[x].push_back(y);
v[y].push_back(x);
}
void dfs(int x,int p,int d,int& i){
par[0][x]=p;
depth[x]=d;
for(auto to:v[x])if(to!=p)dfs(to,x,d+1,i);
ord[x]=i++;
}
void build(){
int i=0;
dfs(0,-1,0,i);
rep(i,h-1){
rep(j,n){
if(par[i][j]<0)par[i+1][j]=-1;
else par[i+1][j]=par[i][par[i][j]];
}
}
}
int lca(int u,int v){
if(depth[u]>depth[v])swap(u,v);
rep(i,h)if((depth[v]-depth[u])>>i &1)v=par[i][v];
if(u==v)return u;
for(int i=h-1;i>=0;i--){
if(par[i][u]!=par[i][v]){
u=par[i][u];
v=par[i][v];
}
}
return par[0][u];
}
int dist(int u,int v){
return depth[u]+depth[v]-2*depth[lca(u,v)];
}
};
int main(){
int n;
cin>>n;
LCA lca(n);
rep(i,n-1){
int x,y;
cin>>x>>y;
lca.add_edge(x-1, y-1);
}
lca.build();
int q;
cin>>q;
rep(aaa,q){
int m,k;scanf("%d%d",&m,&k);
vector<pint> w;
rep(i,m){
int r;scanf("%d",&r);
r--;
w.push_back({lca.ord[r],r});
}
sort(w.begin(),w.end());
int ans=-1;
rep(i,m-k+1){
int ret=lca.lca(w[i].second,w[i+k-1].second);
ans=max(ans,lca.depth[ret]);
}
printf("%d\n",ans);
}
return 0;
}
Submission Info
Submission Time
2018-08-07 01:27:46+0900
Task
F - 根付き木のみさわさん
User
tempura0224
Language
C++14 (GCC 5.4.1)
Score
20
Code Size
2042 Byte
Status
RE
Exec Time
3566 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int m,k;scanf("%d%d",&m,&k);
^
./Main.cpp:90:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int r;scanf("%d",&r);
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
Score / Max Score
0 / 0
20 / 20
0 / 110
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt, sample_03.txt
Subtask1
sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt
Subtask2
sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
1 ms
256 KB
sample_02.txt
AC
1 ms
256 KB
sample_03.txt
AC
1 ms
256 KB
subtask_01_01.txt
AC
1 ms
256 KB
subtask_01_02.txt
AC
1 ms
256 KB
subtask_01_03.txt
AC
1 ms
256 KB
subtask_01_04.txt
AC
2 ms
256 KB
subtask_01_05.txt
AC
13 ms
384 KB
subtask_01_06.txt
AC
1 ms
256 KB
subtask_01_07.txt
AC
2 ms
256 KB
subtask_01_08.txt
AC
11 ms
384 KB
subtask_01_09.txt
AC
1 ms
256 KB
subtask_01_10.txt
AC
2 ms
256 KB
subtask_01_11.txt
AC
11 ms
384 KB
subtask_01_12.txt
AC
1 ms
256 KB
subtask_01_13.txt
AC
2 ms
256 KB
subtask_01_14.txt
AC
11 ms
384 KB
subtask_01_15.txt
AC
1 ms
256 KB
subtask_01_16.txt
AC
2 ms
256 KB
subtask_01_17.txt
AC
12 ms
384 KB
subtask_01_18.txt
AC
1 ms
256 KB
subtask_01_19.txt
AC
2 ms
256 KB
subtask_01_20.txt
AC
10 ms
384 KB
subtask_01_21.txt
AC
1 ms
256 KB
subtask_01_22.txt
AC
2 ms
256 KB
subtask_01_23.txt
AC
13 ms
384 KB
subtask_01_24.txt
AC
1 ms
256 KB
subtask_01_25.txt
AC
2 ms
256 KB
subtask_01_26.txt
AC
11 ms
384 KB
subtask_02_01.txt
TLE
2564 ms
-920608 KB
subtask_02_02.txt
RE
1674 ms
-919964 KB
subtask_02_03.txt
TLE
2519 ms
-919124 KB
subtask_02_04.txt
RE
2034 ms
-919972 KB
subtask_02_05.txt
RE
1798 ms
-919096 KB
subtask_02_06.txt
RE
1587 ms
-919204 KB
subtask_02_07.txt
RE
1588 ms
-919324 KB
subtask_02_08.txt
TLE
2532 ms
-919136 KB
subtask_02_09.txt
TLE
3566 ms
-919168 KB
subtask_02_10.txt
TLE
2577 ms
-919192 KB
subtask_02_11.txt
TLE
3151 ms
-919708 KB
subtask_02_12.txt
RE
1684 ms
-919476 KB
subtask_02_13.txt
RE
1689 ms
-919140 KB
subtask_02_14.txt
TLE
2523 ms
-919200 KB
subtask_02_15.txt
RE
2035 ms
-918836 KB
subtask_02_16.txt
TLE
3517 ms
-918672 KB
subtask_02_17.txt
TLE
2423 ms
-918692 KB
subtask_02_18.txt
RE
1593 ms
-918616 KB
subtask_02_19.txt
RE
1581 ms
-918692 KB
subtask_02_20.txt
RE
1699 ms
-918560 KB
subtask_02_21.txt
RE
1632 ms
-918688 KB
subtask_02_22.txt
RE
1886 ms
-918792 KB
subtask_02_23.txt
RE
1724 ms
-918740 KB
subtask_02_24.txt
RE
1685 ms
-918720 KB
subtask_02_25.txt
RE
1681 ms
-918676 KB
subtask_02_26.txt
RE
1797 ms
-919220 KB