QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473986#5545. Contingency Planyzkkai#WA 0ms3832kbC++201.7kb2024-07-12 15:23:132024-07-12 15:23:13

Judging History

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

  • [2024-07-12 15:23:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-07-12 15:23:13]
  • 提交

answer

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

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

    vector<vector<int>> adj(n + 1);
    vector<pair<int, int>> edges;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        edges.emplace_back(u, v);
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    vector<int> par(n + 1), dep(n + 1), ans(n + 1), one;
    auto dfs = [&](auto&& self, int cur) -> void {
        if (dep[cur] == 1) one.emplace_back(cur);
        for (int nxt : adj[cur]) {
            if (nxt == par[cur]) continue;
            par[nxt] = cur;
            dep[nxt] = dep[cur] + 1;
            self(self, nxt);
        }
        return;
    };
    
    dfs(dfs, 1);

    for (auto&& [u, v] : edges)
        if (par[u] == v)
            swap(u, v);

    bool ok = 1;
    for (int t = 0; t < n - 1; ++t) {
        int i = edges[t].second;

        if (dep[i] >= 2) ans[i] = 1;
        else {
            if (one.back() != i)
                ans[i] = one.back();
            else {
                for (int j = 2; j <= n; ++j)
                    if (ans[j] == 1 && par[j] != i) {
                        ans[i] = j;
                        break;
                    }

                if (ans[i] == 0) {
                    ok = 0;
                    break;
                }
            }
        }
    }

    if (!ok)
        cout << -1 << '\n';
    else
        for (auto &&[u, v] : edges)
            cout << v << ' ' << ans[v] << '\n';

    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

-1

result:

wrong output format Unexpected end of file - int32 expected