Submission #2966037
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:19:21+0900
Task
F - 根付き木のみさわさん
User
tempura0224
Language
C++14 (GCC 5.4.1)
Score
20
Code Size
2042 Byte
Status
RE
Exec Time
3515 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
384 KB
subtask_01_04.txt
AC
3 ms
384 KB
subtask_01_05.txt
AC
19 ms
384 KB
subtask_01_06.txt
AC
1 ms
384 KB
subtask_01_07.txt
AC
3 ms
384 KB
subtask_01_08.txt
AC
16 ms
384 KB
subtask_01_09.txt
AC
1 ms
384 KB
subtask_01_10.txt
AC
2 ms
384 KB
subtask_01_11.txt
AC
14 ms
384 KB
subtask_01_12.txt
AC
1 ms
384 KB
subtask_01_13.txt
AC
3 ms
384 KB
subtask_01_14.txt
AC
16 ms
384 KB
subtask_01_15.txt
AC
1 ms
384 KB
subtask_01_16.txt
AC
3 ms
384 KB
subtask_01_17.txt
AC
18 ms
384 KB
subtask_01_18.txt
AC
1 ms
384 KB
subtask_01_19.txt
AC
2 ms
384 KB
subtask_01_20.txt
AC
12 ms
384 KB
subtask_01_21.txt
AC
1 ms
384 KB
subtask_01_22.txt
AC
3 ms
384 KB
subtask_01_23.txt
AC
18 ms
384 KB
subtask_01_24.txt
AC
1 ms
384 KB
subtask_01_25.txt
AC
2 ms
384 KB
subtask_01_26.txt
AC
13 ms
384 KB
subtask_02_01.txt
RE
1674 ms
-948160 KB
subtask_02_02.txt
RE
1725 ms
-946440 KB
subtask_02_03.txt
TLE
3515 ms
-946188 KB
subtask_02_04.txt
TLE
2287 ms
-945948 KB
subtask_02_05.txt
RE
1574 ms
-945948 KB
subtask_02_06.txt
RE
1789 ms
-945932 KB
subtask_02_07.txt
RE
1698 ms
-946120 KB
subtask_02_08.txt
RE
1694 ms
-946008 KB
subtask_02_09.txt
RE
1703 ms
-945728 KB
subtask_02_10.txt
RE
1789 ms
-945952 KB
subtask_02_11.txt
RE
1708 ms
-946024 KB
subtask_02_12.txt
RE
1637 ms
-945968 KB
subtask_02_13.txt
RE
1696 ms
-945940 KB
subtask_02_14.txt
RE
1654 ms
-945732 KB
subtask_02_15.txt
RE
1787 ms
-945944 KB
subtask_02_16.txt
RE
1744 ms
-945924 KB
subtask_02_17.txt
RE
1904 ms
-945892 KB
subtask_02_18.txt
RE
1694 ms
-945896 KB
subtask_02_19.txt
RE
1578 ms
-945952 KB
subtask_02_20.txt
RE
1991 ms
-945772 KB
subtask_02_21.txt
RE
1597 ms
-945756 KB
subtask_02_22.txt
RE
1578 ms
-945824 KB
subtask_02_23.txt
TLE
2532 ms
-945816 KB
subtask_02_24.txt
TLE
2521 ms
-945728 KB
subtask_02_25.txt
TLE
2326 ms
-945756 KB
subtask_02_26.txt
RE
1732 ms
-945948 KB