QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113822 | #5545. Contingency Plan | PetroTarnavskyi# | WA | 2ms | 6812kb | C++17 | 1.4kb | 2023-06-19 16:29:23 | 2023-06-19 16:29:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int N = 100447;
vector<PII> g[N];
int deg[N];
PII ans[N];
int root = 0;
int u = -1;
void dfs(int v, int idx, int h = 0)
{
if (h == 0)
{
sort(ALL(g[v]), [&](PII a, PII b)
{
return deg[a.first] > deg[b.first];
});
}
if (h >= 2)
{
if (u == -1) u = v;
ans[idx] = {root, v};
}
int pr = -1, pi = -1;
for (auto& [to, i] :g[v])
{
if (i != idx)
{
dfs(to, i, h + 1);
if (h == 0 && pr != -1)
{
ans[pi] = {pr, to};
}
pi = i;
pr = to;
}
}
if (h == 0)
{
ans[pi] = {pr, u};
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
FOR (i, 0, n - 1)
{
int a, b;
cin >> a >> b;
a--, b--;
g[a].PB({b, i});
g[b].PB({a, i});
deg[a]++, deg[b]++;
}
if (*max_element(deg, deg + n) == n - 1)
{
cout << -1 << '\n';
return 0;
}
while (deg[root] == 1) root++;
dfs(root, -1, 0);
FOR (i, 0, n - 1)
{
cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5796kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
2 3 1 7 1 4 1 5 3 4 1 6
result:
ok AC
Test #2:
score: 0
Accepted
time: 2ms
memory: 5824kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 2ms
memory: 6812kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 6228kb
input:
5 2 1 2 3 2 4 4 5
output:
1 3 3 5 4 1 2 5
result:
wrong answer cycle detected