QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262077#1652. One Pieceucup-team133#WA 122ms21624kbC++172.4kb2023-11-23 15:16:272023-11-23 15:16:29

Judging History

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

  • [2023-11-23 15:16:29]
  • 评测
  • 测评结果：WA
  • 用时：122ms
  • 内存：21624kb
查看
  • [2023-11-23 15:16:27]
  • 提交

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] = n - 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;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3420kb

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: 3452kb

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: 1ms
memory: 3432kb

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: 3404kb

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: 1ms
memory: 3472kb

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: 1ms
memory: 3436kb

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: 3436kb

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: 3432kb

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: 1ms
memory: 3440kb

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: 1ms
memory: 3440kb

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: 3436kb

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: 3436kb

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: 1ms
memory: 3436kb

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: 3452kb

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: 3428kb

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: 0ms
memory: 3376kb

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: 3384kb

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: 0ms
memory: 3436kb

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: 3408kb

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: 3468kb

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: 1ms
memory: 3500kb

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: 3380kb

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: 0ms
memory: 3384kb

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: 1ms
memory: 3400kb

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: 3440kb

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: 3504kb

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: 100ms
memory: 21624kb

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: 122ms
memory: 21312kb

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:

59 84 95 119 134 143 169 170 171 175 205 216 239 265 287 291 297 306 343 352 359 365 428 462 486 505 517 532 579 619 632 670 671 674 676 693 700 715 718 726 727 731 741 745 759 781 796 805 819 828 830 831 836 841 842 856 869 870 874 893 902 923 931 965 974 988 1025 1028 1040 1041 1068 1069 1084 1102...

result:

wrong answer 1st lines differ - expected: '246154 41241 48703 165441 1660...983 249992 249993 249994 249997', found: '59 84 95 119 134 143 169 170 1...983 249992 249993 249994 249997'
English 繁體中文 简体中文

Server Time: 2024-11-29 19:41:06 | OpenSource Project