QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253470#5545. Contingency Planwarner1129WA 28ms10576kbC++202.4kb2023-11-17 01:15:292023-11-17 01:15:29

Judging History

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

  • [2023-11-17 01:15:29]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:10576kb
  • [2023-11-17 01:15:29]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
template<class T> void org(T l, T r) { while (l != r) cerr << ' ' << *l++; cerr << '\n'; }
#define debug(x...) dbg(#x, '=', x, '\n')
#define olist(x...) dbg(#x, '='), org(x)
#else
#define debug(...) ((void)0)
#define olist(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using Pt = pair<i128, i128>;

template<class T>
inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 998244353;

Pt operator+(Pt a, Pt b) { return {a.ff + b.ff, a.ss + b.ss}; }
Pt operator-(Pt a, Pt b) { return {a.ff - b.ff, a.ss - b.ss}; }
i128 operator^(Pt a, Pt b) { return a.ff * b.ss - a.ss * b.ff; }
i128 cro(Pt a, Pt b, Pt c) { return (b - a) ^ (c - a); }

template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }
template<class... T> int add(T... x) { int t{}; return (((t += x) %= mod), ...), t; }
template<class... T> int mul(T... x) { i64 t{1}; return (((t *= x) %= mod), ...), t; }

void solve() {
    int n;
    cin >> n;

    vector G(n, vector<int>{});
    vector<pair<int, int>> edg(n - 1);
    for (auto &[u, v] : edg) {
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int A = edg.back().ff;
    int B = edg.back().ss;

    int C = -1;
    vector<int> dep(n);
    vector<int> to(n);
    function<void(int, int)> dfs = [&](int u, int f) {
        if (dep[u] >= 2) {
            C = u;
            to[u] = A;
        }
        if (dep[u] == 1 and u != B) {
            to[u] = B;
        }
        for (int v : G[u]) if (v != f) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    };
    dfs(A, -1);
    to[B] = C;
    
    if (C == -1) {
        cout << "-1\n";
        return;
    }

    for (auto [u, v] : edg) {
        if (dep[u] < dep[v]) swap(u, v);
        cout << u + 1 << ' ' << to[u] + 1 << '\n';
    }
} 

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

1 4
3 4
2 5
5 3

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 2
3 2
4 2
5 3

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 3
2 3
4 1

result:

ok AC

Test #7:

score: 0
Accepted
time: 5ms
memory: 4636kb

input:

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

output:

2 20000
3 20000
4 20000
5 20000
6 20000
7 20000
8 20000
9 20000
10 20000
11 20000
12 20000
13 20000
14 20000
15 20000
16 20000
17 20000
18 20000
19 20000
20 20000
21 20000
22 20000
23 20000
24 20000
25 20000
26 20000
27 20000
28 20000
29 20000
30 20000
31 20000
32 20000
33 20000
34 20000
35 20000
36...

result:

ok AC

Test #8:

score: 0
Accepted
time: 5ms
memory: 4808kb

input:

20000
7662 1
9205 1
5971 1
1 9886
1 18853
14108 1
998 1
1 14958
7100 1
1 2670
1 18493
13838 1
4644 1
2139 1
1 18540
1 14081
1 16836
1 9357
245 1
242 1
1 13472
1 1471
3792 1
1 17875
13976 1
1 15085
1 17283
15014 1
17477 1
11578 1
18441 1
1 14367
3018 1
1 7186
1 4939
2470 1
2993 1
6175 1
1 19886
1 125...

output:

7662 17029
9205 17029
5971 17029
9886 17029
18853 17029
14108 17029
998 17029
14958 17029
7100 17029
2670 17029
18493 17029
13838 17029
4644 17029
2139 17029
18540 17029
14081 17029
16836 17029
9357 17029
245 17029
242 17029
13472 17029
1471 17029
3792 17029
17875 17029
13976 17029
15085 17029
17283...

result:

ok AC

Test #9:

score: 0
Accepted
time: 5ms
memory: 4644kb

input:

20000
8854 1
15635 1
8088 1
1 12138
12367 1
1 15051
6392 1
15564 1
17334 1
1 10164
8704 1
1 13795
1 10292
12108 1
1 50
4 1
1 18364
13341 1
19203 1
1 3017
1 5133
3499 1
19202 1
1 10304
12975 1
1 17220
1 1716
1 4158
1 16763
1 301
1 16645
8690 1
1 10064
16977 1
1 19618
1 5471
1 8763
3997 1
1 3283
11332...

output:

8854 17288
15635 17288
8088 17288
12138 17288
12367 17288
15051 17288
6392 17288
15564 17288
17334 17288
10164 17288
8704 17288
13795 17288
10292 17288
12108 17288
50 17288
4 17288
18364 17288
13341 17288
19203 17288
3017 17288
5133 17288
3499 17288
19202 17288
10304 17288
12975 17288
17220 17288
17...

result:

ok AC

Test #10:

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

input:

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

output:

1 20000
3 20000
4 20000
5 20000
6 20000
7 20000
8 20000
9 20000
10 20000
11 20000
12 20000
13 20000
14 20000
15 20000
16 20000
17 20000
18 20000
19 20000
20 20000
21 20000
22 20000
23 20000
24 20000
25 20000
26 20000
27 20000
28 20000
29 20000
30 20000
31 20000
32 20000
33 20000
34 20000
35 20000
36...

result:

ok AC

Test #11:

score: 0
Accepted
time: 5ms
memory: 4624kb

input:

20000
1 13291
13291 19998
3314 13291
13291 3339
13291 10237
13244 13291
13291 3392
13291 4459
13291 17335
13291 10356
6124 13291
13291 4470
12896 13291
13291 12094
3309 13291
13319 13291
13291 15658
13291 2305
13291 13710
13291 16520
13291 16234
6697 13291
13291 6686
9187 13291
13291 43
13291 2764
1...

output:

1 1064
19998 1064
3314 1064
3339 1064
10237 1064
13244 1064
3392 1064
4459 1064
17335 1064
10356 1064
6124 1064
4470 1064
12896 1064
12094 1064
3309 1064
13319 1064
15658 1064
2305 1064
13710 1064
16520 1064
16234 1064
6697 1064
6686 1064
9187 1064
43 1064
2764 1064
9061 1064
8113 1064
8449 1064
330...

result:

ok AC

Test #12:

score: 0
Accepted
time: 5ms
memory: 4764kb

input:

20000
4030 5565
1206 5565
5565 8947
4887 5565
14605 5565
5565 2947
5565 9038
5565 5326
5565 9021
11087 5565
5565 19562
895 5565
14653 5565
5565 10803
5565 9750
5565 16331
4689 5565
14307 5565
11631 5565
5565 13244
10554 5565
8112 5565
5565 9394
5565 5945
15279 5565
5565 15512
1334 5565
5565 6025
556...

output:

4030 14227
1206 14227
8947 14227
4887 14227
14605 14227
2947 14227
9038 14227
5326 14227
9021 14227
11087 14227
19562 14227
895 14227
14653 14227
10803 14227
9750 14227
16331 14227
4689 14227
14307 14227
11631 14227
13244 14227
10554 14227
8112 14227
9394 14227
5945 14227
15279 14227
15512 14227
133...

result:

ok AC

Test #13:

score: 0
Accepted
time: 22ms
memory: 10492kb

input:

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

output:

2 100000
3 100000
4 100000
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
11 100000
12 100000
13 100000
14 100000
15 100000
16 100000
17 100000
18 100000
19 100000
20 100000
21 100000
22 100000
23 100000
24 100000
25 100000
26 100000
27 100000
28 100000
29 100000
30 100000
31 100000
32 10000...

result:

ok AC

Test #14:

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

input:

5
2 1
3 2
4 3
5 4

output:

1 5
2 5
3 5
4 1

result:

ok AC

Test #15:

score: 0
Accepted
time: 27ms
memory: 10572kb

input:

100000
21871 1
13678 1
27196 1
70437 1
1 35891
1 43010
28018 1
1 64489
61157 1
1 35572
1 41613
1 73049
93865 1
83507 1
1 92127
86278 1
1 15004
1 44154
2005 1
1 94210
41410 1
1 5886
69836 1
1 24120
1 80802
1 9940
66220 1
66549 1
1 20103
1 5
1 33021
35482 1
76185 1
34850 1
1 55173
1 72488
1 76286
1 99...

output:

21871 63055
13678 63055
27196 63055
70437 63055
35891 63055
43010 63055
28018 63055
64489 63055
61157 63055
35572 63055
41613 63055
73049 63055
93865 63055
83507 63055
92127 63055
86278 63055
15004 63055
44154 63055
2005 63055
94210 63055
41410 63055
5886 63055
69836 63055
24120 63055
80802 63055
99...

result:

ok AC

Test #16:

score: 0
Accepted
time: 28ms
memory: 10576kb

input:

100000
1 12976
28108 1
87682 1
79359 1
16128 1
1 90652
1 55874
27276 1
1 66899
1 10296
1 37870
1 78978
26221 1
28589 1
1 46430
32252 1
22407 1
68230 1
64944 1
1 53457
31023 1
1 57101
1 82578
1 33273
69683 1
64357 1
1 32517
1 45623
1 29497
41082 1
1 43731
1 28620
1 64304
1 23462
1 81982
1 91877
1 309...

output:

12976 78172
28108 78172
87682 78172
79359 78172
16128 78172
90652 78172
55874 78172
27276 78172
66899 78172
10296 78172
37870 78172
78978 78172
26221 78172
28589 78172
46430 78172
32252 78172
22407 78172
68230 78172
64944 78172
53457 78172
31023 78172
57101 78172
82578 78172
33273 78172
69683 78172
...

result:

ok AC

Test #17:

score: 0
Accepted
time: 22ms
memory: 10564kb

input:

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

output:

1 99999
3 99999
4 99999
5 99999
6 99999
7 99999
8 99999
9 99999
10 99999
11 99999
12 99999
13 99999
14 99999
15 99999
16 99999
17 99999
18 99999
19 99999
20 99999
21 99999
22 99999
23 99999
24 99999
25 99999
26 99999
27 99999
28 99999
29 99999
30 99999
31 99999
32 99999
33 99999
34 99999
35 99999
36...

result:

ok AC

Test #18:

score: 0
Accepted
time: 21ms
memory: 10528kb

input:

100000
15924 1
13919 15924
86413 15924
15924 78418
36904 15924
15924 60478
15924 78563
15924 23855
63531 15924
15574 15924
73713 15924
62532 15924
15924 19461
15924 80750
15924 57012
15924 27046
55780 15924
69619 15924
58970 15924
65824 15924
15924 3195
26782 15924
71411 15924
84915 15924
95347 1592...

output:

1 26907
13919 26907
86413 26907
78418 26907
36904 26907
60478 26907
78563 26907
23855 26907
63531 26907
15574 26907
73713 26907
62532 26907
19461 26907
80750 26907
57012 26907
27046 26907
55780 26907
69619 26907
58970 26907
65824 26907
3195 26907
26782 26907
71411 26907
84915 26907
95347 26907
53739...

result:

ok AC

Test #19:

score: 0
Accepted
time: 28ms
memory: 10568kb

input:

100000
40659 47250
51514 40659
40659 83613
16333 40659
25291 40659
40659 61711
40659 37621
40659 66805
40659 59550
67744 40659
40659 46644
40659 21771
40659 98164
40659 6655
75053 40659
90431 40659
40659 58023
48769 40659
11506 40659
19125 40659
52852 40659
98702 40659
53360 40659
40659 3999
66767 4...

output:

47250 86919
51514 86919
83613 86919
16333 86919
25291 86919
61711 86919
37621 86919
66805 86919
59550 86919
67744 86919
46644 86919
21771 86919
98164 86919
6655 86919
75053 86919
90431 86919
58023 86919
48769 86919
11506 86919
19125 86919
52852 86919
98702 86919
53360 86919
3999 86919
66767 86919
82...

result:

ok AC

Test #20:

score: 0
Accepted
time: 6ms
memory: 4728kb

input:

20000
13211 1
1 10767
13211 16998
13211 495
10767 7635
10767 6994
10669 16998
1369 16998
495 4745
722 495
7635 251
3552 7635
7267 6994
6994 1772
10669 18929
10669 9328
3076 1369
1369 14212
4745 284
4745 9599
722 6137
722 10565
15137 251
5349 251
16431 3552
3552 15719
7267 10917
598 7267
19533 1772
1...

output:

1 10376
10767 10376
13211 10376
495 10376
7635 10376
6994 10376
10669 10376
16998 10376
4745 10376
722 10376
251 10376
3552 10376
7267 10376
1772 10376
18929 10376
9328 10376
3076 10376
1369 10376
284 10376
9599 10376
6137 10376
10565 10376
15137 10376
5349 10376
16431 10376
15719 10376
10917 10376
...

result:

ok AC

Test #21:

score: 0
Accepted
time: 6ms
memory: 4628kb

input:

20000
11262 14400
16805 2790
19084 11979
15259 5949
9916 12236
2445 1637
1905 15141
9540 16655
12812 16186
19052 1523
6643 1443
13738 10091
9218 1337
16617 16436
17295 16466
1171 1217
19150 5280
2830 8076
16135 7234
11460 213
8101 341
5438 6331
5029 14871
10725 2090
5998 12241
8902 3420
4340 7265
18...

output:

14400 15050
16805 15050
11979 15050
5949 15050
9916 15050
2445 15050
15141 15050
16655 15050
16186 15050
1523 15050
1443 15050
10091 15050
9218 15050
16617 15050
16466 15050
1217 15050
19150 15050
2830 15050
7234 15050
11460 15050
8101 15050
6331 15050
14871 15050
10725 15050
12241 15050
8902 15050
...

result:

ok AC

Test #22:

score: -100
Wrong Answer
time: 6ms
memory: 4748kb

input:

20000
19272 1
19272 7240
6952 7240
6952 10594
12564 10594
12564 13132
14483 13132
14483 1891
9772 1891
16614 9772
14519 16614
12050 14519
4039 12050
4039 9679
8408 4039
12050 6797
17990 6797
6797 17659
14519 14985
16415 14985
1735 16415
16415 18821
14985 9402
9402 18947
9402 5386
17560 16614
17560 1...

output:

19272 9518
7240 9518
6952 9518
10594 9518
12564 9518
13132 9518
14483 9518
1891 9518
9772 9518
16614 9518
14519 9518
12050 9518
4039 9518
9679 9518
8408 9518
6797 9518
17990 9518
17659 9518
14985 9518
16415 9518
1735 9518
18821 9518
9402 9518
18947 9518
5386 9518
17560 9518
1094 9518
7537 9518
19700...

result:

wrong answer u and v already exists