QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474060#5545. Contingency Planyzkkai#WA 0ms3828kbC++202.0kb2024-07-12 15:52:082024-07-12 15:52:08

Judging History

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

  • [2024-07-12 15:52:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-07-12 15:52:08]
  • 提交

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;
    int tt = 0, aa = 0;
    vector<int> cnt(n + 1);

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

        if (dep[i] >= 2) {
            ans[i] = 1;
            ++aa;
            if (dep[i] == 2)
                ++cnt[par[i]];
        }
        else {
            if (tt != 0)
                ans[i] = tt;
            else if (aa - cnt[i] > 0) {
                for (int j = 2; j <= n; ++j)
                    if (ans[j] == 1 && par[j] != i) {
                        ans[i] = j;
                        tt = i;
                        break;
                    }

            }
            if (tt == 0) {
                if (i == one.back()) {
                    ok = 0;
                    break;
                }
                ans[i] = one.back();
            }             
        }
    }

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

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

-1

result:

wrong output format Unexpected end of file - int32 expected