Submission #2965791
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 ; const ll mod2=1e9+9 ; int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ; int n,h=20; vector<vector<int>> v,par; vector<int> depth; void dfs(int x,int p,int d){ par[0][x]=p; depth[x]=d; for(auto to:v[x])if(to!=p)dfs(to,x,d+1); } void build(){ depth.resize(n); par.assign(h,vector<int>(n,-1)); dfs(0,-1,0); 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 ord[101010]; void dfs2(int x,int p,int& i){ for(auto to:v[x]){ if(to==p)continue; dfs2(to,x,i); } ord[x]=i; i++; } bool cmp(int x,int y){ return ord[x]>ord[y]; } int main(){ cin>>n; v.resize(n); rep(i,n-1){ int x,y; cin>>x>>y; x--;y--; v[x].push_back(y); v[y].push_back(x); } build(); int i=0; dfs2(0,-1,i); int q; cin>>q; rep(aaa,q){ int m,k;cin>>m>>k; vector<int> w; rep(i,m){ int r;cin>>r; w.push_back(r-1); } sort(w.begin(),w.end(),cmp); int ans=-1; rep(i,m-k+1){ int ret=lca(w[i],w[i+k-1]); ans=max(ans,depth[ret]); } cout<<ans<<endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - 根付き木のみさわさん |
User | tempura0224 |
Language | C++14 (GCC 5.4.1) |
Score | 130 |
Code Size | 2164 Byte |
Status | AC |
Exec Time | 328 ms |
Memory | 21496 KB |
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 | 32 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 | 30 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 | 30 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 | 30 ms | 256 KB |
subtask_01_15.txt | AC | 1 ms | 256 KB |
subtask_01_16.txt | AC | 3 ms | 256 KB |
subtask_01_17.txt | AC | 31 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 | 30 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 | 31 ms | 256 KB |
subtask_01_24.txt | AC | 1 ms | 256 KB |
subtask_01_25.txt | AC | 2 ms | 256 KB |
subtask_01_26.txt | AC | 30 ms | 256 KB |
subtask_02_01.txt | AC | 124 ms | 15224 KB |
subtask_02_02.txt | AC | 131 ms | 14584 KB |
subtask_02_03.txt | AC | 152 ms | 14456 KB |
subtask_02_04.txt | AC | 129 ms | 15864 KB |
subtask_02_05.txt | AC | 116 ms | 15096 KB |
subtask_02_06.txt | AC | 140 ms | 14976 KB |
subtask_02_07.txt | AC | 132 ms | 18424 KB |
subtask_02_08.txt | AC | 138 ms | 17912 KB |
subtask_02_09.txt | AC | 155 ms | 17656 KB |
subtask_02_10.txt | AC | 126 ms | 15864 KB |
subtask_02_11.txt | AC | 135 ms | 15096 KB |
subtask_02_12.txt | AC | 160 ms | 15096 KB |
subtask_02_13.txt | AC | 141 ms | 15352 KB |
subtask_02_14.txt | AC | 143 ms | 14840 KB |
subtask_02_15.txt | AC | 159 ms | 14712 KB |
subtask_02_16.txt | AC | 129 ms | 21496 KB |
subtask_02_17.txt | AC | 133 ms | 20856 KB |
subtask_02_18.txt | AC | 163 ms | 20728 KB |
subtask_02_19.txt | AC | 129 ms | 15352 KB |
subtask_02_20.txt | AC | 160 ms | 14712 KB |
subtask_02_21.txt | AC | 168 ms | 14584 KB |
subtask_02_22.txt | AC | 167 ms | 19192 KB |
subtask_02_23.txt | AC | 155 ms | 20728 KB |
subtask_02_24.txt | AC | 179 ms | 17656 KB |
subtask_02_25.txt | AC | 324 ms | 14712 KB |
subtask_02_26.txt | AC | 328 ms | 21112 KB |