QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#115576 | #4926. Where Is the Root? | myrcella | 0 | 8ms | 3508kb | C++14 | 2.2kb | 2023-06-26 11:59:20 | 2023-06-26 11:59:22 |
Judging History
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;
}
详细
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