QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628094#5545. Contingency Planucup-team5062#WA 0ms3844kbC++202.1kb2024-10-10 18:32:502024-10-10 18:32:50

Judging History

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

  • [2024-10-10 18:32:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-10-10 18:32:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> U(N - 1), V(N - 1);
    vector graph(N, vector<int>{});
    for (int i = 0; i < N - 1; ++i) {
        cin >> U[i] >> V[i];
        U[i] -= 1;
        V[i] -= 1;
        graph[U[i]].push_back(V[i]);
        graph[V[i]].push_back(U[i]);
    }

    for (int i = 0; i < N; ++i) {
        if ((int)graph[i].size() == N - 1) {
            cout << -1 << '\n';
            return 0;
        }
    }

    const int root = U[N - 2];
    vector<int> dep(N), par(N, -1);
    auto dfs = [&](auto&& self, int u, int p) -> void {
        for (const int v : graph[u]) if (v != p) {
            dep[v] = dep[u] + 1;
            par[v] = u;
            self(self, v, u);
        }
    };
    dfs(dfs, root, -1);
    for (int i = 0; i < N - 1; ++i) {
        if (dep[U[i]] > dep[V[i]]) {
            swap(U[i], V[i]);
        }
    }
    int deepest = 0, dep1 = -1;
    for (int i = 0; i < N - 1; ++i) {
        if (dep[deepest] < dep[i]) {
            deepest = i;
        }
        if (dep[i] == 1) {
            dep1 = i;
        }
    }
    bool type = false;
    for (int u = deepest; u != root; u = par[u]) {
        if (u == V[N - 2]) {
            type = true;
        }
    }

    vector<pair<int, int>> ans;
    ans.reserve(N - 1);
    if (type) {
        for (int i = 0; i < N - 2; ++i) {
            if (dep[V[i]] == 1) {
                ans.emplace_back(deepest, V[i]);
            } else {
                ans.emplace_back(root, V[i]);
            }
        }
        ans.emplace_back(dep1, V[N - 2]);
    } else {
        for (int i = 0; i < N - 2; ++i) {
            if (dep[V[i]] == 1) {
                ans.emplace_back(V[N - 2], V[i]);
            } else {
                ans.emplace_back(root, V[i]);
            }
        }
        ans.emplace_back(deepest, V[N - 2]);
    }

    assert((int)ans.size() == N - 1);
    for (const auto& [u, v] : ans) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

4 1
4 3
5 2
1 5

result:

ok AC

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3844kb

input:

5
1 4
3 4
4 5
2 5

output:

2 1
2 3
2 4
0 5

result:

wrong answer node is not in range [0, N-1]