QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#589406 | #5545. Contingency Plan | May_27th | WA | 1ms | 5808kb | C++20 | 2.4kb | 2024-09-25 17:43:26 | 2024-09-25 17:43:28 |
Judging History
answer
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int MAXN = 5e5 + 5;
const i64 INF = LLONG_MAX/2;
int N, h[MAXN], candidate;
vector<pair<int, int>> G[MAXN];
vector<pair<int, int>> edges;
void dfs(int u, int par = -1) {
for (auto [id, v] : G[u]) {
if (v != par) {
h[v] = h[u] + 1;
dfs(v, u);
}
}
}
bool SolveFor(int root) {
sort(all(G[root]));
int lastNode = G[root].back().second;
set<int> adj;
for (auto [id, v] : G[lastNode]) {
adj.insert(v);
if (v != 1) {
candidate = v;
}
}
h[root] = 0;
dfs(root);
vector<pair<int, int>> ans;
bool works = true;
int have = -1;
for (int i = 0; i < N - 1; i ++) {
if (h[edges[i].first] > h[edges[i].second]) swap(edges[i].first, edges[i].second);
// cout << edges[i].first << " " << edges[i].second << " " << h[edges[i].first] << " " << h[edges[i].second] << "\n";
if (h[edges[i].second] == 1) {
if (edges[i].second != lastNode) {
// connect to the one next to it
// cout << i << " " << edges[i].second << "\n";
int p = upper_bound(all(G[root]), mp(i, edges[i].second)) - G[root].begin();
ans.pb(mp(G[root][p].second, edges[i].second));
} else {
if (have == -1) {
return false;
}
ans.pb(mp(lastNode, have));
}
} else {
ans.pb(mp(edges[i].second, root));
if (!adj.count(edges[i].second)) {
have = edges[i].second;
}
}
}
for (auto [u, v] : ans) {
cout << u << " " << v << "\n";
}
return true;
}
void Solve(void) {
cin >> N;
for (int i = 0; i < N - 1; i ++) {
int u, v; cin >> u >> v;
edges.pb(mp(u, v));
G[u].pb(mp(i, v));
G[v].pb(mp(i, u));
}
for (int i = 1; i <= N; i ++) {
if (G[i].size() == N - 1) {
// A star graph
cout << -1 << "\n";
return;
}
}
// Try root at 1
// if (!SolveFor(1)) {
// SolveFor(candidate);
// }
SolveFor(1);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(10);
int Tests = 1; // cin >> Tests;
while (Tests --) {
Solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5516kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
3 2 7 1 4 1 5 1 3 5 6 1
result:
ok AC
Test #2:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5808kb
input:
5 2 1 2 3 2 4 4 5
output:
result:
wrong output format Unexpected end of file - int32 expected