QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253471#5545. Contingency Planwarner1129WA 5ms4764kbC++202.4kb2023-11-17 01:16:452023-11-17 01:16:45

Judging History

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

  • [2023-11-17 01:16:45]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:4764kb
  • [2023-11-17 01:16:45]
  • 提交

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 and f != B) {
            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: 3608kb

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

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

input:

5
1 4
3 4
4 5
2 5

output:

1 2
3 2
4 1
5 3

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 3
2 1
4 1

result:

ok AC

Test #7:

score: -100
Wrong Answer
time: 5ms
memory: 4764kb

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:

wrong answer cycle detected