QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397693#8056. Travel 2ErayAC ✓159ms5524kbC++141.8kb2024-04-24 16:00:282024-04-24 16:00:28

Judging History

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

  • [2024-04-24 16:00:28]
  • 评测
  • 测评结果:AC
  • 用时:159ms
  • 内存:5524kb
  • [2024-04-24 16:00:28]
  • 提交

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, &degree);
		// 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, &degree);
		// 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