QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253471 | #5545. Contingency Plan | warner1129 | WA | 5ms | 4764kb | C++20 | 2.4kb | 2023-11-17 01:16:45 | 2023-11-17 01:16:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
template<class T> void org(T l, T r) { while (l != r) cerr << ' ' << *l++; cerr << '\n'; }
#define debug(x...) dbg(#x, '=', x, '\n')
#define olist(x...) dbg(#x, '='), org(x)
#else
#define debug(...) ((void)0)
#define olist(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using Pt = pair<i128, i128>;
template<class T>
inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 998244353;
Pt operator+(Pt a, Pt b) { return {a.ff + b.ff, a.ss + b.ss}; }
Pt operator-(Pt a, Pt b) { return {a.ff - b.ff, a.ss - b.ss}; }
i128 operator^(Pt a, Pt b) { return a.ff * b.ss - a.ss * b.ff; }
i128 cro(Pt a, Pt b, Pt c) { return (b - a) ^ (c - a); }
template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }
template<class... T> int add(T... x) { int t{}; return (((t += x) %= mod), ...), t; }
template<class... T> int mul(T... x) { i64 t{1}; return (((t *= x) %= mod), ...), t; }
void solve() {
int n;
cin >> n;
vector G(n, vector<int>{});
vector<pair<int, int>> edg(n - 1);
for (auto &[u, v] : edg) {
cin >> u >> v;
u--, v--;
G[u].push_back(v);
G[v].push_back(u);
}
int A = edg.back().ff;
int B = edg.back().ss;
int C = -1;
vector<int> dep(n);
vector<int> to(n);
function<void(int, int)> dfs = [&](int u, int f) {
if (dep[u] >= 2 and f != B) {
C = u;
to[u] = A;
}
if (dep[u] == 1 and u != B) {
to[u] = B;
}
for (int v : G[u]) if (v != f) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
};
dfs(A, -1);
to[B] = C;
if (C == -1) {
cout << "-1\n";
return;
}
for (auto [u, v] : edg) {
if (dep[u] < dep[v]) swap(u, v);
cout << u + 1 << ' ' << to[u] + 1 << '\n';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
2 3 7 6 4 3 5 3 1 6 6 5
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
5 2 1 2 3 2 4 4 5
output:
1 4 3 4 2 5 5 3
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
5 1 4 3 4 4 5 2 5
output:
1 2 3 2 4 1 5 3
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
5 5 2 1 2 4 2 3 4
output:
5 3 1 3 2 1 4 1
result:
ok AC
Test #7:
score: -100
Wrong Answer
time: 5ms
memory: 4764kb
input:
20000 1 2 1 3 4 1 5 1 6 1 7 1 1 8 1 9 1 10 1 11 12 1 1 13 14 1 1 15 1 16 17 1 1 18 1 19 20 1 21 1 22 1 1 23 24 1 1 25 26 1 1 27 28 1 29 1 30 1 1 31 1 32 1 33 1 34 1 35 36 1 1 37 1 38 1 39 40 1 41 1 1 42 1 43 44 1 1 45 46 1 1 47 48 1 49 1 1 50 1 51 52 1 53 1 54 1 1 55 56 1 57 1 58 1 1 59 60 1 61 1 1 ...
output:
2 20000 3 20000 4 20000 5 20000 6 20000 7 20000 8 20000 9 20000 10 20000 11 20000 12 20000 13 20000 14 20000 15 20000 16 20000 17 20000 18 20000 19 20000 20 20000 21 20000 22 20000 23 20000 24 20000 25 20000 26 20000 27 20000 28 20000 29 20000 30 20000 31 20000 32 20000 33 20000 34 20000 35 20000 36...
result:
wrong answer cycle detected