QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#186501 | #5545. Contingency Plan | NYCU_Yamada | RE | 1ms | 7500kb | C++20 | 3.7kb | 2023-09-23 23:58:46 | 2023-09-23 23:58:46 |
Judging History
answer
#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada
const int MAXN = 1e5+5;
vector<pii> e[MAXN];
int n, C;
bitset<MAXN> label;
int head[MAXN], connect[MAXN], fa[MAXN];
void dfs(int x, int p) {
fa[x] = p;
for (auto it : e[x]) {
int to = it.X, eid = it.Y;
if (to == p) continue;
head[eid] = to;
dfs(to, x);
}
}
pair<bool, vector<pii>> cal(int root) {
label.reset();
vector<pii> ret;
vector<int> ok;
for (int i = 0; i <= n; ++i) {
head[i] = 0;
connect[i] = 0;
fa[i] = 0;
}
for (int i = 0; i < SZ(e[root]); ++i) {
int to = e[root][i].X, eid = e[root][i].Y;
if (i == SZ(e[root]) - 1) {
C = to;
}
else {
connect[to] = e[root][i+1].X;
}
head[eid] = to;
dfs(to, root);
}
for (int i = 0; i < n-1; ++i) {
int cur = head[i];
if (cur == C) {
if (!SZ(ok)) return pair<bool, vector<pii>>(false, vector<pii>());
ret.eb(cur, ok[0]);
}
else {
if (connect[cur] == 0) {
ret.eb(cur, root);
if (fa[cur] != C) ok.eb(cur);
}
else {
ret.eb(cur, connect[cur]);
}
}
}
return pair<bool, vector<pii>>(true, ret);
}
void solve() {
cin >> n;
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
e[u].eb(v, i), e[v].eb(u, i);
}
for (int i = 1; i <= n; ++i) {
if (SZ(e[i]) == n-1) {
cout << -1 << endl;
return;
}
sort(ALL(e[i]), [&](const pii &a, const pii &b){
return a.Y < b.Y;
});
}
int root = 1;
pair<bool, vector<pii>> ans = cal(root);
if (ans.X == false) {
for (auto it : e[C]) {
if (it.X == 1) continue;
root = it.X;
break;
}
assert(root != 1);
ans = cal(root);
}
assert(ans.X == true);
for (auto it : ans.Y) cout << it.X << ' ' << it.Y << endl;
}
signed main() {
IOS();
int t = 1; // cin >> t;
for (int i=1;i<=t;++i) solve();
return 0;
}
#else
#ifdef cold66
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = priority_queue<T>;
template <typename T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define X first
#define Y second
template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
template <typename... U> Vec(int n = 0, U ... _u) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(_u...)) {}
};
template <typename T> struct Vec<1, T> : vector<T> {
Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};
#ifdef local
#define IOS() void()
#define debug(...) \
fprintf(stderr, "\u001b[33m"), \
fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << endl;}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define endl '\n'
#endif
template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}
#endif
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6816kb
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: 1ms
memory: 6756kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 7500kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: -100
Runtime Error
input:
5 2 1 2 3 2 4 4 5