Submission #2966076
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((1<<h)<n)h++;
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 k=0;
dfs(0,-1,0,k);
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:39:49+0900
Task
F - 根付き木のみさわさん
User
tempura0224
Language
C++14 (GCC 5.4.1)
Score
130
Code Size
2045 Byte
Status
AC
Exec Time
127 ms
Memory
18552 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
110 / 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
9 ms
256 KB
subtask_01_06.txt
AC
1 ms
256 KB
subtask_01_07.txt
AC
2 ms
256 KB
subtask_01_08.txt
AC
8 ms
256 KB
subtask_01_09.txt
AC
1 ms
256 KB
subtask_01_10.txt
AC
2 ms
256 KB
subtask_01_11.txt
AC
8 ms
256 KB
subtask_01_12.txt
AC
1 ms
256 KB
subtask_01_13.txt
AC
2 ms
256 KB
subtask_01_14.txt
AC
8 ms
256 KB
subtask_01_15.txt
AC
1 ms
256 KB
subtask_01_16.txt
AC
2 ms
256 KB
subtask_01_17.txt
AC
8 ms
256 KB
subtask_01_18.txt
AC
1 ms
256 KB
subtask_01_19.txt
AC
2 ms
256 KB
subtask_01_20.txt
AC
8 ms
256 KB
subtask_01_21.txt
AC
1 ms
256 KB
subtask_01_22.txt
AC
2 ms
256 KB
subtask_01_23.txt
AC
8 ms
256 KB
subtask_01_24.txt
AC
1 ms
256 KB
subtask_01_25.txt
AC
1 ms
256 KB
subtask_01_26.txt
AC
8 ms
256 KB
subtask_02_01.txt
AC
108 ms
14712 KB
subtask_02_02.txt
AC
103 ms
13560 KB
subtask_02_03.txt
AC
106 ms
13432 KB
subtask_02_04.txt
AC
95 ms
15224 KB
subtask_02_05.txt
AC
95 ms
13944 KB
subtask_02_06.txt
AC
99 ms
13944 KB
subtask_02_07.txt
AC
105 ms
16632 KB
subtask_02_08.txt
AC
107 ms
15864 KB
subtask_02_09.txt
AC
111 ms
15352 KB
subtask_02_10.txt
AC
98 ms
15096 KB
subtask_02_11.txt
AC
113 ms
13816 KB
subtask_02_12.txt
AC
114 ms
13816 KB
subtask_02_13.txt
AC
115 ms
14840 KB
subtask_02_14.txt
AC
114 ms
14072 KB
subtask_02_15.txt
AC
114 ms
13688 KB
subtask_02_16.txt
AC
104 ms
18552 KB
subtask_02_17.txt
AC
104 ms
17528 KB
subtask_02_18.txt
AC
110 ms
17144 KB
subtask_02_19.txt
AC
105 ms
14840 KB
subtask_02_20.txt
AC
124 ms
13688 KB
subtask_02_21.txt
AC
119 ms
13432 KB
subtask_02_22.txt
AC
125 ms
17144 KB
subtask_02_23.txt
AC
118 ms
17656 KB
subtask_02_24.txt
AC
127 ms
15352 KB
subtask_02_25.txt
AC
122 ms
13560 KB
subtask_02_26.txt
AC
122 ms
17528 KB