Submission #3177643
Source Code Expand
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int n,k,K,q,m,dp[200005],vs[200005],pre[200005],pro[200005],seg[1<<20],sg[1<<20],ans;
vector<int>g[100005];
vector<int>w;
int rmin(int a,int b){
if(dp[a]<dp[b])return a;
else return b;
}
int rmax(int a,int b){
if(dp[a]>dp[b])return a;
else return b;
}
void dfs(int v,int p,int d){
pro[v]=k;
pre[v]=k;
dp[k]=d;
vs[k++]=v;
for(int i=0;i<g[v].size();i++){
int u=g[v][i];
if(u!=p){
dfs(u,v,d+1);
pro[v]=k;
dp[k]=d;
vs[k++]=v;
}
}
}
void add(int a,int x){
a+=(1<<19)-1;
seg[a]+=x;
while(a>0){
a=(a-1)/2;
seg[a]=(seg[a*2+1]+seg[a*2+2]);
}
}
int sum(int a,int b,int l,int r,int o){
if(r<a||b<l)return 0;
if(a<=l&&r<=b)return seg[o];
return sum(a,b,l,(l+r-1)/2,o*2+1)+sum(a,b,(l+r+1)/2,r,o*2+2);
}
void up(int a,int x){
a+=(1<<19)-1;
sg[a]=rmin(sg[a],x);
while(a>0){
a=(a-1)/2;
sg[a]=rmin(sg[a*2+1],sg[a*2+2]);
}
}
int que(int a,int b,int l,int r,int o){
if(r<a||b<l)return K;
if(a<=l&&r<=b)return sg[o];
return rmin(que(a,b,l,(l+r-1)/2,o*2+1),que(a,b,(l+r+1)/2,r,o*2+2));
}
int lca(int a,int b){
if(b<a)swap(a,b);
return que(a,b,0,(1<<19)-1,0);
}
void update(int a){
if(sum(pre[vs[a]],pro[vs[a]],0,(1<<19)-1,0)>=k){
ans=rmax(ans,a);
}
}
int main(void){
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
g[--a].PB(--b);
g[b].PB(a);
}
dfs(0,-1,0);
dp[k]=n;
K=k;
for(int i=0;i<1<<20;i++)sg[i]=k;
for(int i=0;i<K;i++){
up(i,i);
}
scanf("%d",&q);
while(q){
ans=0;
scanf("%d%d",&m,&k);
w.clear();
for(int i=0;i<m;i++){
int a;
scanf("%d",&a);
a--;
w.PB(pre[a]);
add(pre[a],1);
}
sort(w.begin(),w.end());
for(int i=0;i<w.size();i++)update(w[i]);
int c;
for(int i=1;i<w.size();i++){
c=lca(w[i],w[i-1]);
update(c);
}
for(int i=0;i<w.size();i++){
add(w[i],-1);
}
printf("%d\n",dp[ans]);
q--;
}
}
Submission Info
Submission Time |
|
Task |
F - 根付き木のみさわさん |
User |
nxteru |
Language |
C++14 (GCC 5.4.1) |
Score |
130 |
Code Size |
2728 Byte |
Status |
AC |
Exec Time |
170 ms |
Memory |
25472 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:83:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:86:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
./Main.cpp:97:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:100:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&m,&k);
^
./Main.cpp:104:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
...
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 |
5 ms |
12544 KB |
sample_02.txt |
AC |
4 ms |
12544 KB |
sample_03.txt |
AC |
4 ms |
12544 KB |
subtask_01_01.txt |
AC |
4 ms |
12544 KB |
subtask_01_02.txt |
AC |
4 ms |
12544 KB |
subtask_01_03.txt |
AC |
4 ms |
12544 KB |
subtask_01_04.txt |
AC |
6 ms |
12544 KB |
subtask_01_05.txt |
AC |
28 ms |
12544 KB |
subtask_01_06.txt |
AC |
5 ms |
12544 KB |
subtask_01_07.txt |
AC |
6 ms |
12544 KB |
subtask_01_08.txt |
AC |
23 ms |
12544 KB |
subtask_01_09.txt |
AC |
4 ms |
12544 KB |
subtask_01_10.txt |
AC |
6 ms |
12544 KB |
subtask_01_11.txt |
AC |
23 ms |
12544 KB |
subtask_01_12.txt |
AC |
4 ms |
12544 KB |
subtask_01_13.txt |
AC |
6 ms |
12544 KB |
subtask_01_14.txt |
AC |
23 ms |
12544 KB |
subtask_01_15.txt |
AC |
5 ms |
12544 KB |
subtask_01_16.txt |
AC |
7 ms |
12544 KB |
subtask_01_17.txt |
AC |
26 ms |
12544 KB |
subtask_01_18.txt |
AC |
5 ms |
12544 KB |
subtask_01_19.txt |
AC |
6 ms |
12544 KB |
subtask_01_20.txt |
AC |
25 ms |
12544 KB |
subtask_01_21.txt |
AC |
5 ms |
12544 KB |
subtask_01_22.txt |
AC |
6 ms |
12544 KB |
subtask_01_23.txt |
AC |
26 ms |
12544 KB |
subtask_01_24.txt |
AC |
5 ms |
12544 KB |
subtask_01_25.txt |
AC |
6 ms |
12544 KB |
subtask_01_26.txt |
AC |
26 ms |
12544 KB |
subtask_02_01.txt |
AC |
125 ms |
17660 KB |
subtask_02_02.txt |
AC |
139 ms |
17280 KB |
subtask_02_03.txt |
AC |
145 ms |
17152 KB |
subtask_02_04.txt |
AC |
118 ms |
18304 KB |
subtask_02_05.txt |
AC |
134 ms |
17792 KB |
subtask_02_06.txt |
AC |
137 ms |
17664 KB |
subtask_02_07.txt |
AC |
144 ms |
21628 KB |
subtask_02_08.txt |
AC |
153 ms |
21376 KB |
subtask_02_09.txt |
AC |
159 ms |
21120 KB |
subtask_02_10.txt |
AC |
139 ms |
18428 KB |
subtask_02_11.txt |
AC |
153 ms |
17920 KB |
subtask_02_12.txt |
AC |
157 ms |
17920 KB |
subtask_02_13.txt |
AC |
131 ms |
17788 KB |
subtask_02_14.txt |
AC |
143 ms |
17536 KB |
subtask_02_15.txt |
AC |
143 ms |
17408 KB |
subtask_02_16.txt |
AC |
146 ms |
25468 KB |
subtask_02_17.txt |
AC |
156 ms |
25088 KB |
subtask_02_18.txt |
AC |
170 ms |
24960 KB |
subtask_02_19.txt |
AC |
131 ms |
17788 KB |
subtask_02_20.txt |
AC |
143 ms |
17408 KB |
subtask_02_21.txt |
AC |
150 ms |
17280 KB |
subtask_02_22.txt |
AC |
151 ms |
22652 KB |
subtask_02_23.txt |
AC |
165 ms |
24960 KB |
subtask_02_24.txt |
AC |
167 ms |
21120 KB |
subtask_02_25.txt |
AC |
117 ms |
17408 KB |
subtask_02_26.txt |
AC |
134 ms |
25472 KB |