QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113821 | #5549. Game Show | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 1.4kb | 2023-06-19 16:24:53 | 2023-06-19 16:24:54 |
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 (to != v)
{
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: 0
Runtime Error
input:
4 4 2 3 -4 3 1 2 7 -1 1 3 3 1 1 4 1 1