QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262085#1652. One Pieceucup-team133#WA 106ms21596kbC++172.4kb2023-11-23 15:22:542023-11-23 15:22:55

Judging History

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

  • [2023-11-23 15:22:55]
  • 评测
  • 测评结果：WA
  • 用时：106ms
  • 内存：21596kb
查看
  • [2023-11-23 15:22:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int mnd = *min_element(d.begin(), d.end());
    vector<int> r;
    for (int i = 0; i < n; i++) {
        if (d[i] == mnd) {
            r.emplace_back(i);
        }
    }
    vector<int> f(n);
    if (r.size() == 2) {
        vector<int> b(n), c(n);
        function<void(int, int)> Dfs = [&](int v, int p) {
            if (d[v] == mnd * 2 - 1) {
                c[b[v]]++;
            }
            for (int to: g[v]) {
                if (to == p) {
                    continue;
                }
                b[to] = b[v];
                Dfs(to, v);
            }
        };
        b[r[0]] = r[0];
        b[r[1]] = r[1];
        Dfs(r[0], r[1]);
        Dfs(r[1], r[0]);
        for (int i = 0; i < n; i++) {
            if (d[i] < mnd * 2 - 1) {
                f[i] = n + 10;
            } else if (d[i] == mnd * 2 - 1) {
                f[i] = c[b[i]];
            } else {
                f[i] = n + 20;
            }
        }
    } else if (r.size() == 1) {
        vector<int> b(n), c(n);
        function<void(int, int)> Dfs = [&](int v, int p) {
            if (d[v] == mnd * 2 - 1) {
                c[b[v]]++;
            }
            for (int to: g[v]) {
                if (to == p) {
                    continue;
                }
                b[to] = b[v];
                Dfs(to, v);
            }
        };
        for (int t: g[r[0]]) {
            b[t] = t;
            Dfs(t, r[0]);
        }
        for (int i = 0; i < n; i++) {
            if (d[i] < mnd * 2) {
                f[i] = n + 10;
            } else if (d[i] == mnd * 2) {
                f[i] = c[b[i]];
            } else {
                f[i] = n + 20;
            }
        }
    } else {
        assert(false);
    }
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    sort(ans.begin(), ans.end(), [&](int i, int j) {
        return make_pair(f[i], i) < make_pair(f[j], j);
    });
    for (int i = 0; i < n; i++) {
        cout << ans[i] + 1 << " \n"[i == n - 1];
    }
    return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

5
1 2
1 3
2 4
2 5
2 2 3 3 3

output:

3 4 5 1 2

result:

ok single line: '3 4 5 1 2'

Test #2:

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

input:

4
2 1
3 2
3 4
1 0 1 2

output:

2 1 3 4

result:

ok single line: '2 1 3 4'

Test #3:

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

input:

1
0

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

2
1 2
0 1

output:

1 2

result:

ok single line: '1 2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

3
2 3
1 2
2 1 1

output:

2 3 1

result:

ok single line: '2 3 1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

4
3 2
1 4
3 1
1 3 2 1

output:

1 4 2 3

result:

ok single line: '1 4 2 3'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3380kb

input:

4
4 3
4 2
1 2
3 2 2 1

output:

2 3 4 1

result:

ok single line: '2 3 4 1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3372kb

input:

4
3 2
1 2
4 1
1 2 3 1

output:

1 4 2 3

result:

ok single line: '1 4 2 3'

Test #9:

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

input:

4
3 1
2 3
2 4
3 1 2 0

output:

4 1 2 3

result:

ok single line: '4 1 2 3'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3400kb

input:

4
2 4
3 4
1 4
2 2 2 1

output:

1 2 3 4

result:

ok single line: '1 2 3 4'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

5
4 5
2 3
2 1
5 3
4 3 2 1 1

output:

4 5 1 2 3

result:

ok single line: '4 5 1 2 3'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

5
2 5
3 1
3 4
3 5
0 3 1 2 2

output:

1 2 3 4 5

result:

ok single line: '1 2 3 4 5'

Test #13:

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

input:

5
2 3
2 5
1 3
1 4
1 3 2 1 4

output:

1 4 2 3 5

result:

ok single line: '1 4 2 3 5'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

5
3 4
1 2
2 5
3 2
3 2 2 3 3

output:

4 1 5 2 3

result:

ok single line: '4 1 5 2 3'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

5
5 1
3 2
5 4
5 3
3 3 2 3 2

output:

2 1 4 3 5

result:

ok single line: '2 1 4 3 5'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3400kb

input:

6
2 4
6 2
5 2
5 3
1 4
1 1 3 0 2 2

output:

4 1 2 3 5 6

result:

ok single line: '4 1 2 3 5 6'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3380kb

input:

6
3 5
5 6
4 2
2 1
6 1
3 4 3 5 2 2

output:

1 3 5 6 2 4

result:

ok single line: '1 3 5 6 2 4'

Test #18:

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

input:

6
5 2
6 5
6 3
4 6
2 1
2 1 4 4 2 3

output:

1 5 2 3 4 6

result:

ok single line: '1 5 2 3 4 6'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

6
1 6
5 6
1 4
2 4
3 5
2 4 2 3 1 1

output:

5 6 1 2 3 4

result:

ok single line: '5 6 1 2 3 4'

Test #20:

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

input:

6
4 5
1 3
6 3
3 2
3 5
2 2 1 3 2 2

output:

1 2 5 6 3 4

result:

ok single line: '1 2 5 6 3 4'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3428kb

input:

7
7 6
7 5
4 1
3 2
4 7
2 7
3 3 4 2 3 3 2

output:

1 2 5 6 4 7 3

result:

ok single line: '1 2 5 6 4 7 3'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3376kb

input:

7
6 7
4 1
3 6
4 7
6 2
5 2
2 3 3 1 4 2 1

output:

4 7 1 2 3 5 6

result:

ok single line: '4 7 1 2 3 5 6'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

7
7 5
4 7
6 7
1 2
3 7
7 2
2 1 2 2 2 2 1

output:

2 7 1 3 4 5 6

result:

ok single line: '2 7 1 3 4 5 6'

Test #24:

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

input:

7
4 7
4 1
4 2
5 3
3 7
3 6
2 1 3 1 4 4 2

output:

2 4 1 3 5 6 7

result:

ok single line: '2 4 1 3 5 6 7'

Test #25:

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

input:

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

output:

1 3 5 7 4 2 6 8

result:

ok single line: '1 3 5 7 4 2 6 8'

Test #26:

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

input:

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

output:

6 8 1 2 3 4 5 7

result:

ok single line: '6 8 1 2 3 4 5 7'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

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

output:

4 5 1 2 3 6 7 8

result:

ok single line: '4 5 1 2 3 6 7 8'

Test #28:

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

input:

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

output:

1 2 3 7 8 4 5 6

result:

ok single line: '1 2 3 7 8 4 5 6'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

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

output:

1 3 4 8 2 6 5 7

result:

ok single line: '1 3 4 8 2 6 5 7'

Test #30:

score: 0
Accepted
time: 92ms
memory: 21596kb

input:

250000
27197 102813
107013 109797
16583 152577
164884 11838
214586 173971
248203 141910
7896 111843
80520 130209
6277 128026
55601 234265
95559 88739
152936 50808
194534 24226
159232 83111
103712 33855
142546 246859
40404 81467
125784 239727
24202 165110
57020 155999
133375 118407
156303 150104
1493...

output:

10 23 36 42 44 70 71 101 111 113 116 141 177 183 204 217 221 251 252 253 260 264 271 272 307 318 325 328 338 360 397 423 429 442 494 506 518 521 526 537 564 567 602 633 673 683 721 738 739 744 754 770 827 835 837 865 872 890 893 914 946 948 967 973 981 1003 1014 1063 1068 1083 1118 1133 1152 1166 11...

result:

ok single line: '10 23 36 42 44 70 71 101 111 1...950 249954 249976 249982 249986'

Test #31:

score: -100
Wrong Answer
time: 106ms
memory: 21328kb

input:

250000
198658 122606
213093 143827
45640 230664
242707 66336
228202 70151
54424 136589
31088 11371
216202 169155
131901 199050
54921 227981
114533 38096
180601 164687
21723 12006
68933 157358
93093 147993
50664 240700
41575 183691
172663 45572
194543 35989
237102 202526
171096 138704
245144 179222
2...

output:

246154 48703 166068 41241 165441 10620 29728 53554 73909 93188 124031 198484 203298 232580 232961 47764 67652 88266 98241 104150 110913 276 10358 19783 23479 31195 34746 39213 50180 56872 58013 61730 72498 74789 76927 81541 92649 99820 107747 149482 160127 165828 167312 176787 177991 179363 183317 1...

result:

wrong answer 1st lines differ - expected: '246154 41241 48703 165441 1660...983 249992 249993 249994 249997', found: '246154 48703 166068 41241 1654...983 249992 249993 249994 249997'
English 繁體中文 简体中文

伺服器時間: 2024-11-29 21:42:16 | 開源專案