QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#477008 | #5545. Contingency Plan | karuna# | WA | 1ms | 3568kb | C++20 | 1.2kb | 2024-07-13 22:21:58 | 2024-07-13 22:21:58 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 101010;
int n, u[SZ], v[SZ], deg[SZ];
vector<int> g[SZ];
int dep[SZ], par[SZ];
void dfs(int p, int v) {
for (int x : g[v]) if (p != x) {
dep[x] = dep[v] + 1;
par[x] = v;
dfs(v, x);
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n - 1; i++) {
cin >> u[i] >> v[i];
deg[u[i]]++;
deg[v[i]]++;
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for (int i = 1; i <= n; i++) if (deg[i] == n - 1) return !(cout << "-1\n");
int pos = -1;
for (int i = 1; i <= n; i++) {
if (deg[i] == 1 && i != u[0] && i != v[0]) {
pos = i;
break;
}
}
if (pos == -1) return !(cout << "-1\n");
dfs(-1, pos);
vector<pii> V;
for (int i = 0; i < n - 1; i++) {
if (dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
if (u[i] == pos) {
int x = max_element(dep + 1, dep + 1 + n) - dep;
V.push_back({v[i], x});
}
else {
V.push_back({pos, v[i]});
}
}
for (auto [u, v] : V) {
cout << u << ' ' << v << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3552kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
4 1 4 7 2 6 4 5 4 3 4 6
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3568kb
input:
5 2 1 2 3 2 4 4 5
output:
3 1 2 5 3 4 3 5
result:
wrong answer cycle detected