QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115576#4926. Where Is the Root?myrcella0 8ms3508kbC++142.2kb2023-06-26 11:59:202023-06-26 11:59:22

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:59:22]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:3508kb
  • [2023-06-26 11:59:20]
  • 提交

answer

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

typedef long long LL;

#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}

const int maxn = 555;

int n;
int deg[maxn];
vector <int> edge[maxn];

vector <int> leaf, candidate;

int main() {
  // freopen("input.txt","r",stdin);
  cin >> n;
  rep(i, 1, n) {
	int u, v;
	cin >> u >> v;
	edge[u].pb(v);
	edge[v].pb(u);
	deg[u]++;
	deg[v]++;
  }
  rep(i, 1, n + 1) {
	if (deg[i] == 1) continue;
	cout << "? " << n - 1;
    rep(j, 1, n + 1) if (i != j) cout << " " << j;
    cout << endl;
    cout.flush();
    string s;
    cin >> s;
    if (s == "NO") {
	  cout << "! " << i << endl;
	  cout.flush();
	  return 0;
	}
  }
  // root is a leaf
  rep(i, 1, n + 1) if (deg[i] == 1) {
	for (int v : edge[i]) if (SZ(edge[v]) >= 3) {
	  cout << "? 2 ";
	  int x = edge[v][0], y = edge[v][1];
	  if (x == i) x = edge[v][2];
	  else if (y == i) y = edge[v][2];
	  cout << x << " " << y << endl;
	  string s;
	  cin >> s;
	  
	  if (s == "YES") break;
	  
	  cout << "? 3 " << x << " " << y << " " << i << endl;
	  string s1;
	  cin >> s1;
	  if (s1 == "YES") {
		cout << "! " << i << endl;
		return 0;
	  }
	  break;
	}
  }
  rep(i, 1, n + 1) {
	if (deg[i] == 1) leaf.pb(i);
	else candidate.pb(i);
  }
  while (SZ(candidate) > 1) {
	int mid = SZ(candidate)/2;
    cout << "? ";
    for (auto it : leaf) cout << it << " ";
    rep(i, 0, mid) cout << candidate[i] << " ";
    cout << endl; cout.flush();
    string s; cin >> s;
    if (s == "YES") {
	  while (SZ(candidate) > mid) candidate.pop_back();
	}
    else {
	  vector <int> tmp;
	  rep(i, mid, SZ(candidate)) tmp.pb(candidate[i]);
	  candidate = tmp;
	}
  }
  cout << "! " << candidate[0] << endl;
  cout.flush();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 1ms
memory: 3420kb

input:

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

output:

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

result:

ok OK

Test #2:

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

input:

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

output:

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

result:

ok OK

Test #3:

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

input:

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

output:

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

result:

ok OK

Test #4:

score: -7
Wrong Answer
time: 0ms
memory: 3436kb

input:

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

output:

? 8 2 3 4 5 6 7 8 9
? 8 1 2 3 5 6 7 8 9
? 8 1 2 3 4 6 7 8 9
? 8 1 2 3 4 5 6 8 9
? 8 1 2 3 4 5 6 7 9
? 8 1 2 3 4 5 6 7 8
? 2 4 1
? 2 3 6 1 4 5 
? 2 3 6 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: 3508kb

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
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES

output:

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

result:

ok OK

Test #25:

score: 0
Accepted
time: 2ms
memory: 3412kb

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
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES

output:

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

result:

ok OK

Test #26:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

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

output:

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

result:

ok OK

Test #27:

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

input:

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

output:

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

result:

ok OK

Test #28:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

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

output:

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

result:

ok OK

Test #29:

score: -10
Wrong Answer
time: 2ms
memory: 3468kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 27
Acceptable Answer
time: 2ms
memory: 3476kb

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:

? 499 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

points 0.32530120480 OK

Test #55:

score: 0
Wrong Answer
time: 8ms
memory: 3428kb

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:

? 499 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

wrong output format Unexpected end of file - int32 expected