QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397693 | #8056. Travel 2 | Eray | AC ✓ | 159ms | 5524kb | C++14 | 1.8kb | 2024-04-24 16:00:28 | 2024-04-24 16:00:28 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 2500 + 5;
int n;
int d[N];
std::vector<int> unvis[N];
std::vector<int> to[N];
std::map<int, int> eid[N];
void solve(int u) {
while(true) {
// printf("solve %d\n", u);
if(unvis[u].empty()) break;
int id = unvis[u].back();
unvis[u].pop_back();
printf("> %d\n", id);
fflush(stdout);
int v, degree;
scanf("%d%d", &v, °ree);
// printf("Found edge %d -> %d (%d)\n", u, v, id);
to[u][id] = v, eid[u][v] = id;
u = v;
if(!d[u]) {
// printf("Found new vertice %d!\n", u);
d[u] = degree;
for(int i = 1; i <= degree; i++) unvis[u].emplace_back(i);
to[u].resize(degree + 1);
n = std::max(n, u);
}
}
}
bool vis[N];
void dfs(int u) {
vis[u] = true;
// printf("dfs %d\n", u);
solve(u);
for(int i = 1; i <= d[u]; i++) {
int v = to[u][i];
if(vis[v]) continue;
printf("> %d\n", i);
fflush(stdout);
// printf("Existing edge %d -> %d (%d)\n", u, v, eid[u][v]);
scanf("%*d%*d");
dfs(v);
printf("> %d\n", eid[v][u]);
// printf("Existing edge %d -> %d (%d)\n", v, u, eid[v][u]);
fflush(stdout);
scanf("%*d%*d");
}
}
int main() {
int T; scanf("%d", &T);
while(T--) {
n = 0;
int rt, degree;
scanf("%d%d", &rt, °ree);
// printf("Found new vertice %d!\n", rt);
d[rt] = degree;
for(int i = 1; i <= degree; i++) unvis[rt].emplace_back(i);
to[rt].resize(degree + 1);
n = std::max(n, rt);
dfs(rt);
printf("! ");
for(int u = 1; u <= n; u++) for(int i = 1; i <= d[u]; i++) if(u < to[u][i]) printf("%d %d ", u, to[u][i]);
puts("");
fflush(stdout);
char result[100];
scanf("%s", result);
if(strcmp(result, "Correct")) return 0;
for(int i = 1; i <= n; i++) d[i] = 0, to[i].clear(), unvis[i].clear(), eid[i].clear(), vis[i] = false;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4084kb
input:
2 1 1 2 1 1 1 2 1 1 1 Correct 1 3 4 2 2 2 4 2 1 3 3 1 1 3 2 2 1 3 2 2 4 2 2 2 1 3 3 1 1 3 Correct
output:
> 1 > 1 > 1 > 1 ! 1 2 > 3 > 2 > 2 > 1 > 2 > 1 > 1 > 1 > 1 > 2 > 2 > 1 > 2 > 1 ! 1 2 1 3 1 4 2 4
result:
ok correct! (2 test cases)
Test #2:
score: 0
Accepted
time: 124ms
memory: 4092kb
input:
1000 1 9 10 6 3 9 6 9 4 9 9 8 4 9 6 9 7 7 6 9 9 8 6 9 3 9 7 7 9 8 7 7 3 9 8 8 4 9 2 7 4 9 5 8 4 9 8 8 6 9 8 8 3 9 10 6 6 9 5 8 7 7 5 8 6 9 10 6 4 9 10 6 8 8 7 7 8 8 9 8 8 8 10 6 2 7 9 8 2 7 5 8 3 9 5 8 2 7 6 9 2 7 10 6 1 9 9 8 5 8 9 8 3 9 2 7 3 9 9 8 1 9 8 8 5 8 8 8 1 9 7 7 4 9 7 7 1 9 6 9 1 9 5 8 1...
output:
> 9 > 6 > 9 > 9 > 9 > 8 > 8 > 8 > 7 > 7 > 7 > 6 > 8 > 6 > 6 > 5 > 7 > 8 > 7 > 7 > 6 > 8 > 5 > 7 > 5 > 6 > 6 > 5 > 4 > 7 > 4 > 6 > 3 > 4 > 4 > 3 > 5 > 3 > 4 > 5 > 3 > 2 > 6 > 4 > 5 > 5 > 5 > 4 > 4 > 2 > 3 > 1 > 8 > 3 > 3 > 2 > 4 > 2 > 3 > 1 > 7 > 2 > 2 > 1 > 6 > 2 > 3 > 1 > 5 > 1 > 4 > 1 > 3 > 2 > 2 ...
result:
ok correct! (1000 test cases)
Test #3:
score: 0
Accepted
time: 159ms
memory: 4164kb
input:
500 1 19 20 6 12 7 18 7 12 7 20 6 17 10 20 6 9 7 3 7 9 7 15 8 9 7 17 10 9 7 20 6 15 8 19 7 15 8 5 7 14 9 10 9 14 9 5 7 15 8 8 4 18 7 8 4 15 8 6 7 7 11 2 8 7 11 12 7 7 11 19 7 10 9 4 8 10 9 19 7 7 11 14 9 7 11 10 9 2 8 10 9 7 11 6 7 14 9 18 7 2 8 18 7 14 9 2 8 11 8 2 8 14 9 6 7 15 8 16 7 17 10 16 7 1...
output:
> 19 > 6 > 7 > 7 > 6 > 5 > 10 > 4 > 7 > 7 > 6 > 8 > 5 > 9 > 4 > 3 > 7 > 7 > 6 > 7 > 9 > 9 > 8 > 6 > 5 > 4 > 6 > 3 > 4 > 7 > 11 > 8 > 10 > 5 > 9 > 6 > 8 > 8 > 7 > 5 > 8 > 7 > 7 > 6 > 7 > 5 > 6 > 6 > 6 > 5 > 6 > 4 > 5 > 5 > 8 > 4 > 4 > 5 > 3 > 7 > 8 > 6 > 4 > 4 > 3 > 5 > 2 > 2 > 6 > 7 > 5 > 3 > 4 > 7 ...
result:
ok correct! (500 test cases)
Test #4:
score: 0
Accepted
time: 126ms
memory: 4204kb
input:
100 1 99 100 4 29 11 100 4 8 8 72 8 8 8 57 5 8 8 9 9 71 8 9 9 8 8 82 7 23 6 82 7 29 11 82 7 8 8 100 4 55 9 75 10 84 5 75 10 21 4 75 10 16 7 75 10 55 9 41 7 55 9 76 9 33 5 52 6 93 10 26 10 93 10 52 6 46 6 52 6 33 5 76 9 55 9 96 10 24 10 62 12 97 8 62 12 24 10 96 10 49 5 92 13 49 5 67 10 49 5 96 10 42...
output:
> 99 > 4 > 11 > 3 > 8 > 8 > 7 > 5 > 6 > 9 > 8 > 8 > 5 > 7 > 6 > 6 > 10 > 5 > 4 > 2 > 9 > 10 > 5 > 9 > 4 > 8 > 7 > 7 > 8 > 7 > 7 > 9 > 5 > 6 > 10 > 10 > 9 > 5 > 6 > 4 > 4 > 8 > 6 > 10 > 10 > 12 > 8 > 11 > 9 > 9 > 5 > 13 > 4 > 10 > 3 > 8 > 5 > 7 > 4 > 4 > 7 > 3 > 7 > 7 > 6 > 2 > 3 > 10 > 9 > 11 > 8 > ...
result:
ok correct! (100 test cases)
Test #5:
score: 0
Accepted
time: 147ms
memory: 4840kb
input:
10 1 999 1000 10 80 7 1000 10 856 9 1000 10 485 11 675 7 662 10 675 7 485 11 466 6 485 11 867 5 485 11 1000 10 674 4 752 6 436 7 752 6 674 4 611 8 525 6 611 8 371 8 34 9 371 8 528 6 530 11 528 6 371 8 611 8 606 6 791 11 606 6 33 6 606 6 467 7 606 6 732 6 34 9 119 10 34 9 732 6 628 12 455 7 628 12 73...
output:
> 999 > 10 > 7 > 9 > 9 > 8 > 11 > 7 > 10 > 6 > 10 > 6 > 9 > 5 > 8 > 7 > 4 > 6 > 7 > 5 > 3 > 8 > 6 > 7 > 8 > 9 > 7 > 6 > 11 > 5 > 6 > 6 > 6 > 11 > 5 > 6 > 4 > 7 > 3 > 6 > 8 > 10 > 7 > 5 > 12 > 7 > 11 > 4 > 2 > 5 > 7 > 11 > 9 > 10 > 8 > 9 > 4 > 11 > 3 > 8 > 7 > 9 > 13 > 8 > 6 > 7 > 9 > 10 > 7 > 9 > 8 ...
result:
ok correct! (10 test cases)
Test #6:
score: 0
Accepted
time: 146ms
memory: 5500kb
input:
4 1 999 1000 25 684 16 987 21 684 16 14 23 767 14 333 26 767 14 374 21 767 14 14 23 684 16 261 22 917 21 952 20 917 21 261 22 684 16 902 23 656 21 902 23 684 16 269 16 62 16 450 29 930 19 450 29 62 16 269 16 684 16 1000 25 798 24 287 28 307 23 287 28 134 20 737 14 134 20 842 19 134 20 547 18 134 20 ...
output:
> 999 > 25 > 16 > 21 > 15 > 23 > 14 > 26 > 13 > 21 > 12 > 22 > 14 > 22 > 21 > 20 > 20 > 21 > 13 > 23 > 21 > 22 > 12 > 16 > 16 > 29 > 19 > 28 > 15 > 15 > 11 > 24 > 24 > 28 > 23 > 27 > 20 > 14 > 19 > 19 > 18 > 18 > 17 > 26 > 15 > 13 > 14 > 25 > 19 > 23 > 18 > 22 > 17 > 24 > 23 > 14 > 22 > 19 > 21 > 18...
result:
ok correct! (4 test cases)
Test #7:
score: 0
Accepted
time: 149ms
memory: 5244kb
input:
4 1 199 200 102 92 110 200 102 12 94 184 90 12 94 23 104 12 94 200 102 189 101 80 96 189 101 50 94 189 101 188 101 110 97 188 101 189 101 96 99 98 95 96 99 189 101 200 102 88 102 172 100 88 102 66 108 117 106 66 108 150 105 36 104 150 105 144 109 150 105 46 102 150 105 66 108 88 102 143 91 40 91 127...
output:
> 199 > 102 > 110 > 101 > 94 > 90 > 93 > 104 > 92 > 100 > 101 > 96 > 100 > 94 > 99 > 101 > 97 > 100 > 98 > 99 > 95 > 98 > 97 > 99 > 102 > 100 > 101 > 108 > 106 > 107 > 105 > 104 > 104 > 109 > 103 > 102 > 102 > 106 > 100 > 91 > 91 > 103 > 90 > 108 > 89 > 90 > 86 > 97 > 99 > 96 > 85 > 89 > 99 > 101 > ...
result:
ok correct! (4 test cases)
Test #8:
score: 0
Accepted
time: 85ms
memory: 5524kb
input:
4 1 140 141 140 140 140 141 140 139 140 141 140 138 140 141 140 137 140 141 140 136 140 141 140 135 140 141 140 134 140 141 140 133 140 141 140 132 140 141 140 131 140 141 140 130 140 141 140 129 140 141 140 128 140 141 140 127 140 141 140 126 140 141 140 125 140 141 140 124 140 141 140 123 140 141 ...
output:
> 140 > 140 > 140 > 139 > 140 > 138 > 140 > 137 > 140 > 136 > 140 > 135 > 140 > 134 > 140 > 133 > 140 > 132 > 140 > 131 > 140 > 130 > 140 > 129 > 140 > 128 > 140 > 127 > 140 > 126 > 140 > 125 > 140 > 124 > 140 > 123 > 140 > 122 > 140 > 121 > 140 > 120 > 140 > 119 > 140 > 118 > 140 > 117 > 140 > 116 ...
result:
ok correct! (4 test cases)
Test #9:
score: 0
Accepted
time: 51ms
memory: 4976kb
input:
4 1 2498 2499 2 2500 2498 2499 2 1 2498 2498 2 2500 2498 2498 2 1 2498 2497 2 2500 2498 2497 2 1 2498 2496 2 2500 2498 2496 2 1 2498 2495 2 2500 2498 2495 2 1 2498 2494 2 2500 2498 2494 2 1 2498 2493 2 2500 2498 2493 2 1 2498 2492 2 2500 2498 2492 2 1 2498 2491 2 2500 2498 2491 2 1 2498 2490 2 2500 ...
output:
> 2498 > 2 > 2498 > 1 > 2497 > 2 > 2497 > 1 > 2496 > 2 > 2496 > 1 > 2495 > 2 > 2495 > 1 > 2494 > 2 > 2494 > 1 > 2493 > 2 > 2493 > 1 > 2492 > 2 > 2492 > 1 > 2491 > 2 > 2491 > 1 > 2490 > 2 > 2490 > 1 > 2489 > 2 > 2489 > 1 > 2488 > 2 > 2488 > 1 > 2487 > 2 > 2487 > 1 > 2486 > 2 > 2486 > 1 > 2485 > 2 > 2...
result:
ok correct! (4 test cases)
Extra Test:
score: 0
Extra Test Passed