QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115543#4926. Where Is the Root?jamielim0 8ms3768kbC++143.1kb2023-06-26 11:26:542023-06-26 11:26:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 11:26:57]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:3768kb
  • [2023-06-26 11:26:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const ll MOD=1000000007;

int n;
vector<int> adj[505];
int dist[2][505];
int fr;
int dep[505];
int maxdep;
vector<int> leaf;

void findFakeRoot(){
	for(int i=1;i<=n;i++)dist[0][i]=dist[1][i]=INF;
	dist[0][1]=0;
	queue<int> q;
	q.push(1);
	int maxi=1;
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i:adj[cur]){
			if(dist[0][i]>dist[0][cur]+1){
				dist[0][i]=dist[0][cur]+1;
				q.push(i);
				if(dist[0][i]>dist[0][maxi])maxi=i;
			}
		}
	}
	dist[1][maxi]=0;
	q.push(maxi);
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i:adj[cur]){
			if(dist[1][i]>dist[1][cur]+1){
				dist[1][i]=dist[1][cur]+1;
				q.push(i);
				if(dist[1][i]>dist[1][maxi])maxi=i;
			}
		}
	}
	fr=maxi;
	while(dist[1][fr]>dist[1][maxi]/2){
		for(int i:adj[fr]){
			if(dist[1][i]==dist[1][fr]-1){
				fr=i;break;
			}
		}
	}
}

void dfs(int x,int p){
	maxdep=max(maxdep,dep[x]);
	int c=0;
	for(int i:adj[x]){
		if(i==p)continue;
		dep[i]=dep[x]+1;
		dfs(i,x);
		c++;
	}
	if(c==0)leaf.pb(x);
}

vector<int> t;
void dfs2(int x,int p,int avoid){
	int c=0;
	for(int i:adj[x]){
		if(i==p)continue;
		if(i==avoid)continue;
		dfs2(i,x,avoid);
		c++;
	}
	if(c==0)t.pb(x);
}
vector<int> getOtherLeaves(int x){
	t.clear();
	dfs2(fr,0,x);
	return t;
}

bool query(vector<int> v){
	sort(ALL(v));
	v.resize(unique(ALL(v))-v.begin());
	printf("? %d",SZ(v));
	for(int i:v)printf(" %d",i);
	printf("\n");
	fflush(stdout);
	char str[5];
	scanf("%s",str);
	if(str[0]=='Y')return 1;
	return 0;
}

int main(){
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		adj[a].pb(b);adj[b].pb(a);
	}
	findFakeRoot();
	dfs(fr,0);
	int l=0,r=maxdep;
	while(l<r){
		int m=(l+r+1)/2;
		vector<int> v;
		for(int i=1;i<=n;i++){
			if(dep[i]>=m)v.pb(i);
		}
		if(query(v))l=m;
		else r=m-1;
	}
	if(l==0){
		printf("! %d\n",fr);
		fflush(stdout);
		return 0;
	}
	vector<int> v,perm;
	for(int i=1;i<=n;i++)if(dep[i]==l)v.pb(i);
	if(SZ(v)==1){
		printf("! %d\n",v[0]);
		fflush(stdout);
		return 0;
	}
	while(SZ(v)>2){
		int m=(SZ(v)+1)/2;
		vector<int> q;
		for(int i=0;i<m;i++){
			q.pb(v[i]);
		}
		for(int i:perm)q.pb(i);
		if(query(q)){
			for(int i=m;i<SZ(v);i++)perm.pb(v[i]);
			while(SZ(v)>m)v.pop_back();
		}else{
			for(int i=0;i<m;i++)perm.pb(v[i]);
			vector<int> tmp;
			for(int i=m;i<SZ(v);i++)tmp.pb(v[i]);
			v=tmp;
		}
	}
	vector<int> l0=getOtherLeaves(v[0]);
	vector<int> l1=getOtherLeaves(v[1]);
	int ans=v[0];
	if(SZ(l0)>=2){
		l0.pb(v[0]);
		if(query(l0)){
			ans=v[0];
		}else{
			ans=v[1];
		}
	}else{
		l1.pb(v[1]);
		if(query(l1)){
			ans=v[1];
		}else{
			ans=v[0];
		}
	}
	printf("! %d\n",ans);
	printf("! %d\n",ans);
	fflush(stdout);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 0ms
memory: 3724kb

input:

7
4 1
1 2
4 3
3 5
3 6
4 7
NO

output:

? 6 1 2 3 5 6 7
! 4

result:

ok OK

Test #2:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

9
5 9
8 6
2 8
1 8
3 6
6 7
1 4
4 5
YES
NO
YES
YES

output:

? 6 2 3 5 6 7 9
? 3 3 7 9
? 2 2 5
? 4 2 3 7 9
! 2
! 2

result:

ok OK

Test #3:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

9
6 8
2 5
5 1
4 3
5 9
6 3
6 1
7 5
NO
YES
NO
YES

output:

? 5 2 4 5 7 9
? 8 1 2 3 4 5 7 8 9
? 2 1 3
? 5 2 4 7 8 9
! 8
! 8

result:

ok OK

Test #4:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

9
1 8
9 4
7 8
5 7
3 9
2 5
9 1
4 6
YES
YES
YES

output:

? 6 2 3 4 5 6 9
? 4 2 3 4 6
? 1 6
! 6

result:

ok OK

Test #5:

score: -7
Wrong Answer
time: 1ms
memory: 3684kb

input:

9
7 1
8 4
2 8
5 2
2 3
1 2
1 9
9 6
NO
YES
YES
YES

output:

? 4 4 6 7 9
? 8 1 3 4 5 6 7 8 9
? 2 1 3
? 4 1 3 4 5
! 1
! 1

result:

wrong output format Unexpected end of file - int32 expected

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 10
Accepted
time: 0ms
memory: 3692kb

input:

30
1 15
29 30
1 4
7 28
29 17
1 26
26 7
12 5
27 13
3 7
27 1
21 15
9 22
22 5
24 27
19 1
25 30
22 27
6 15
16 13
18 2
27 10
27 30
20 26
8 15
18 8
14 1
27 23
11 3
YES
NO
NO
YES
NO
YES

output:

? 23 2 3 5 6 7 8 9 10 11 12 13 16 17 18 20 21 22 23 24 25 28 29 30
? 12 2 3 5 9 11 12 16 17 18 25 28 29
? 6 6 7 8 10 13 20
? 9 6 7 8 10 13 20 21 22 23
? 10 6 7 8 10 13 20 21 22 24 30
? 17 2 4 6 9 10 11 12 14 16 17 19 20 21 23 24 25 28
! 23
! 23

result:

ok OK

Test #25:

score: -10
Wrong Answer
time: 1ms
memory: 3768kb

input:

30
15 16
8 6
19 2
26 17
30 15
26 4
1 6
1 23
15 1
29 25
21 3
12 1
2 24
29 22
9 1
3 10
27 28
5 12
20 5
14 7
5 26
7 18
10 23
1 28
3 11
7 1
19 23
13 23
29 30
YES
NO
YES
NO
YES

output:

? 22 2 3 4 5 8 10 11 13 14 16 17 18 19 20 21 22 24 25 26 27 29 30
? 12 2 3 4 11 17 20 21 22 24 25 26 29
? 5 5 8 10 13 14
? 8 5 8 10 16 18 19 27 30
? 15 4 8 9 11 13 14 16 17 18 20 21 22 24 25 27
! 13
! 13

result:

wrong output format Unexpected end of file - int32 expected

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 66
Acceptable Answer
time: 6ms
memory: 3700kb

input:

500
419 133
44 225
391 269
419 461
293 347
108 31
110 363
423 257
321 155
498 87
180 492
251 5
357 30
341 172
275 109
372 446
286 336
208 339
162 320
138 103
129 219
62 141
359 286
130 238
470 460
418 48
210 358
429 13
323 143
382 415
406 394
309 175
325 170
128 108
6 113
363 17
470 457
7 224
288 48...

output:

? 306 2 6 7 8 9 13 14 15 16 19 24 26 27 29 30 31 34 35 36 37 39 40 42 44 47 48 50 52 53 55 56 57 59 60 62 63 67 68 70 72 74 75 77 78 79 80 82 85 86 87 88 91 94 95 97 98 103 107 108 109 111 112 113 114 118 119 120 121 122 126 127 128 129 131 134 135 136 138 140 141 142 144 145 146 148 149 150 151 153...

result:

points 0.79518072290 OK

Test #55:

score: 83
Accepted
time: 8ms
memory: 3716kb

input:

500
188 321
193 4
334 269
259 66
121 396
73 153
332 477
263 67
178 262
185 377
175 53
462 245
390 337
387 200
445 92
387 159
135 263
323 312
143 374
252 47
375 382
303 345
345 283
150 1
66 289
462 82
317 201
169 423
154 193
486 251
368 305
357 375
107 443
437 348
64 55
408 465
315 469
186 328
197 39...

output:

? 240 3 5 8 9 10 14 17 19 20 21 22 24 27 30 31 34 36 39 40 43 45 46 47 49 50 54 55 56 57 60 64 65 67 68 69 70 71 72 76 77 78 79 84 87 88 89 90 91 92 95 96 101 102 103 106 108 113 114 116 117 119 120 122 123 125 128 129 130 131 135 137 139 140 141 147 148 151 152 154 157 158 160 162 167 169 171 172 1...

result:

ok OK

Test #56:

score: 63
Acceptable Answer
time: 0ms
memory: 3668kb

input:

500
423 179
253 294
3 58
24 345
129 8
428 443
349 246
15 286
367 428
272 290
294 230
144 239
403 270
354 110
17 157
441 227
216 226
220 211
199 353
397 445
204 269
234 452
283 355
58 375
500 400
284 11
388 235
385 21
53 124
77 290
395 235
71 351
300 26
109 326
462 215
87 405
116 196
430 136
481 390
...

output:

? 279 2 6 8 9 12 15 17 18 19 24 25 26 28 29 30 34 35 37 41 42 43 45 46 49 51 53 56 57 60 63 64 68 72 74 75 76 78 79 80 81 82 84 85 86 87 89 90 91 95 96 98 99 100 101 102 106 109 110 112 113 114 115 116 117 118 119 120 121 124 125 126 127 128 129 130 131 132 136 137 138 139 140 141 142 143 144 146 14...

result:

points 0.75903614460 OK

Test #57:

score: 0
Wrong Answer
time: 5ms
memory: 3636kb

input:

500
246 390
321 345
385 319
393 475
36 188
453 174
35 111
420 55
411 304
78 250
483 12
241 37
295 498
348 52
105 329
321 255
222 272
457 247
262 189
239 31
114 489
45 321
269 380
493 340
287 128
248 33
201 388
12 379
231 65
94 241
85 43
262 391
154 156
92 140
58 117
44 166
284 480
290 44
157 393
32 ...

output:

? 306 4 5 6 7 9 10 13 15 17 18 19 20 23 25 26 28 29 30 34 37 38 39 40 41 45 46 49 50 51 54 57 59 60 61 62 63 67 68 69 75 76 78 79 80 83 84 85 89 90 91 92 94 95 96 99 101 102 103 104 105 107 109 110 112 115 116 117 119 121 122 123 125 126 127 128 130 132 133 134 138 139 140 141 145 147 149 151 155 15...

result:

wrong output format Unexpected end of file - int32 expected