QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140497#1139. StationsQwerty12320 208ms3744kbC++201.7kb2023-08-16 00:48:152023-08-16 00:48:18

Judging History

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

  • [2023-08-16 00:48:18]
  • 评测
  • 测评结果：0
  • 用时：208ms
  • 内存：3744kb
查看
  • [2023-08-16 00:48:15]
  • 提交

stations

#include "stations.h"

#include <bits/stdc++.h>

#include <cassert>
#include <vector>

constexpr int N = 1e3;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    std::vector<std::vector<int>> gr(n);
    for (int i = 0; i < n - 1; i++) {
        gr[u[i]].push_back(v[i]);
        gr[v[i]].push_back(u[i]);
    }
    std::vector<int> res(n);
    auto dfs = [&](auto dfs, int v, int f, int d, int& e) -> void {
        for (int t : gr[v]) {
            if (t != f) {
                dfs(dfs, t, v, d + 1, e);
            }
        }
        res[v] = e++;
    };
    for (int i = 0; i < n; i++) {
        res[i] = i;
    }

    return res;
}

int find_next_station(int s, int dest, std::vector<int> c) {
    assert(s != dest);
    for (int to : c) {
        if (to == dest) {
            return to;
        }
    }
    // if (c.size() == 1) {
    //     return c.front();
    // }

    int n = N + 10;
    static std::vector<std::vector<int>> gr;
    if (gr.size() == 0) {
        gr.assign(n, {});
        for (int i = 1; i < n; i++) {
            int u = i;
            int v = i / 2;
            gr[u].push_back(v);
            gr[v].push_back(u);
        }
    }
    auto dfs = [&](auto dfs, int v, int f) -> bool {
        if (v == dest) {
            return true;
        }
        for (int t : gr[v]) {
            if (t != f) {
                if (dfs(dfs, t, v)) {
                    return true;
                }
            }
        }
        return false;
    };
    for (int t : c) {
        if (dfs(dfs, t, s)) {
            return t;
        }
    }

    assert(false);
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Stage 2: Program stations Dangerous Syscalls

Test #1:

score: 0
Stage 2: Program stations Dangerous Syscalls

input:

10
10 1000
4 5
9 0
2 6
5 2
8 3
1 4
8 1
6 0
3 7
5575
4 6 5
7 3 3
6 0 0
8 5 1
7 1 3
0 4 6
0 5 6
0 8 6
1 6 4
4 5 5
4 8 1
4 3 1
8 9 1
4 8 1
2 7 5
4 6 5
6 9 0
6 9 0
8 0 1
7 2 3
1 0 4
1 8 8
7 2 3
6 8 2
6 8 2
9 6 0
6 0 0
0 9 9
2 5 5
9 6 0
2 0 6
0 9 9
2 9 6
3 6 8
2 0 6
0 1 6
5 8 4
1 2 4
1 6 4
3 6 8
6 4 2
0 ...

output:

10
0
1
2
3
4
5
6
7
8
9
3
0
1
2
998
0
1
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...

input:

output:

result:

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 208ms
memory: 3744kb

input:

0
10
996 1000
0 1
2 0
1 3
4 1
5 2
6 2
7 3
3 8
4 9
10 4
11 5
12 5
6 13
14 6
7 15
7 16
17 8
18 8
19 9
9 20
21 10
10 22
23 11
24 11
12 25
26 12
27 13
13 28
14 29
30 14
15 31
15 32
16 33
34 16
35 17
17 36
18 37
38 18
39 19
40 19
41 20
42 20
43 21
44 21
45 22
46 22
23 47
48 23
49 24
24 50
25 51
52 25
26 ...

output:

996
0
1
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
10...

input:

1
50252
876 174 1
437
937 71 1
468
508 771 1
253
715 87 1
357
940 154 1
469
721 974 1
360
864 867 1
431
728 899 1
363
433 888 3
216
867
868
235 92 3
117
471
472
508 517 1
253
404 582 3
201
809
810
902 767 1
450
712 486 1
355
655 0 1
327
545 583 1
272
471 488 3
235
943
944
40 666 3
19
81
82
691 417 1...

output:

437
468
253
357
469
360
431
363
216
117
253
201
450
355
327
272
235
19
345
495
489
471
433
35
349
484
307
445
426
59
29
237
448
345
81
382
407
111
330
370
233
357
126
239
178
132
147
106
465
143
147
347
486
268
231
61
338
490
205
155
212
480
302
366
471
417
22
280
321
308
443
106
405
138
14
13
461
3...

result:

wrong answer Diff at 18-th number: read 19 but expected 82

Subtask #3:

score: 0
Stage 2: Program stations Dangerous Syscalls

Test #17:

score: 0
Stage 2: Program stations Dangerous Syscalls

input:

10
2 1000000
1 0
10000
1 0 0
1 0 0
0 1 1
1 0 0
0 1 1
0 1 1
1 0 0
0 1 1
1 0 0
1 0 0
0 1 1
0 1 1
0 1 1
1 0 0
1 0 0
0 1 1
1 0 0
1 0 0
0 1 1
1 0 0
0 1 1
1 0 0
0 1 1
0 1 1
1 0 0
0 1 1
0 1 1
1 0 0
1 0 0
1 0 0
0 1 1
1 0 0
1 0 0
1 0 0
0 1 1
1 0 0
1 0 0
0 1 1
0 1 1
1 0 0
0 1 1
1 0 0
1 0 0
0 1 1
1 0 0
0 1 1
1...

output:

2
0
1
997
0
1
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
...

input:

output:

result:

Subtask #4:

score: 0
Stage 2: Program stations Dangerous Syscalls

Test #34:

score: 10
Accepted
time: 54ms
memory: 3708kb

input:

0
10
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1

output:

2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1

input:

1
100000
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0...

output:

0
1
1
0
1
0
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
1
1
1
0
0
1
1
0
0
0
1
1
0
1
1
0
1
1
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
1
1
1
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
1
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
1
0
0
0
0
1
0
0
1
0
0
0
...

result:

ok

Test #35:

score: 0
Stage 2: Program stations Dangerous Syscalls

input:

10
3 1000000000
2 1
2 0
7475
1 0 2
1 2 2
2 1 1
0 2 2
2 0 0
0 1 2
1 2 2
2 1 1
0 2 2
1 0 2
0 2 2
0 2 2
0 2 2
0 2 2
2 0 0
1 2 2
2 1 1
1 0 2
0 1 2
0 1 2
0 1 2
1 0 2
1 2 2
2 1 1
0 1 2
1 2 2
1 0 2
0 2 2
2 1 1
1 0 2
2 1 1
0 2 2
0 1 2
1 0 2
2 1 1
1 0 2
2 1 1
1 0 2
1 0 2
1 0 2
1 2 2
1 2 2
0 1 2
1 0 2
1 0 2
1...

output:

3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2

input:

output:

result:

Subtask #5:

score: 0
Stage 2: Program stations Dangerous Syscalls

Test #54:

score: 0
Stage 2: Program stations Dangerous Syscalls

input:

10
3 1000000000
1 0
2 1
7507
1 2 2
2 0 1
1 2 2
1 2 2
1 2 2
0 2 1
0 2 1
2 1 1
2 1 1
0 2 1
1 0 0
1 0 0
1 0 0
2 0 1
1 0 0
0 1 1
0 1 1
0 2 1
2 0 1
2 0 1
2 0 1
0 2 1
2 0 1
1 0 0
2 0 1
0 1 1
2 0 1
1 2 2
2 0 1
0 2 1
0 2 1
0 2 1
0 2 1
2 0 1
0 1 1
2 0 1
0 1 1
0 2 1
0 2 1
2 0 1
2 0 1
1 2 2
0 2 1
2 0 1
2 0 1
2...

output:

3
0
1
2
998
0
1
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
9...

input:

output:

result:
English 繁體中文 简体中文

Server Time: 2024-11-29 12:34:20 | OpenSource Project