QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474060 | #5545. Contingency Plan | yzkkai# | WA | 0ms | 3828kb | C++20 | 2.0kb | 2024-07-12 15:52:08 | 2024-07-12 15:52:08 |
Judging History
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