QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253470 | #5545. Contingency Plan | warner1129 | WA | 28ms | 10576kb | C++20 | 2.4kb | 2023-11-17 01:15:29 | 2023-11-17 01:15:29 |
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) {
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: 3828kb
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: 1ms
memory: 3824kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
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: 3608kb
input:
5 1 4 3 4 4 5 2 5
output:
1 2 3 2 4 2 5 3
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 5 2 1 2 4 2 3 4
output:
5 3 1 3 2 3 4 1
result:
ok AC
Test #7:
score: 0
Accepted
time: 5ms
memory: 4636kb
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:
ok AC
Test #8:
score: 0
Accepted
time: 5ms
memory: 4808kb
input:
20000 7662 1 9205 1 5971 1 1 9886 1 18853 14108 1 998 1 1 14958 7100 1 1 2670 1 18493 13838 1 4644 1 2139 1 1 18540 1 14081 1 16836 1 9357 245 1 242 1 1 13472 1 1471 3792 1 1 17875 13976 1 1 15085 1 17283 15014 1 17477 1 11578 1 18441 1 1 14367 3018 1 1 7186 1 4939 2470 1 2993 1 6175 1 1 19886 1 125...
output:
7662 17029 9205 17029 5971 17029 9886 17029 18853 17029 14108 17029 998 17029 14958 17029 7100 17029 2670 17029 18493 17029 13838 17029 4644 17029 2139 17029 18540 17029 14081 17029 16836 17029 9357 17029 245 17029 242 17029 13472 17029 1471 17029 3792 17029 17875 17029 13976 17029 15085 17029 17283...
result:
ok AC
Test #9:
score: 0
Accepted
time: 5ms
memory: 4644kb
input:
20000 8854 1 15635 1 8088 1 1 12138 12367 1 1 15051 6392 1 15564 1 17334 1 1 10164 8704 1 1 13795 1 10292 12108 1 1 50 4 1 1 18364 13341 1 19203 1 1 3017 1 5133 3499 1 19202 1 1 10304 12975 1 1 17220 1 1716 1 4158 1 16763 1 301 1 16645 8690 1 1 10064 16977 1 1 19618 1 5471 1 8763 3997 1 1 3283 11332...
output:
8854 17288 15635 17288 8088 17288 12138 17288 12367 17288 15051 17288 6392 17288 15564 17288 17334 17288 10164 17288 8704 17288 13795 17288 10292 17288 12108 17288 50 17288 4 17288 18364 17288 13341 17288 19203 17288 3017 17288 5133 17288 3499 17288 19202 17288 10304 17288 12975 17288 17220 17288 17...
result:
ok AC
Test #10:
score: 0
Accepted
time: 0ms
memory: 4596kb
input:
20000 1 2 2 3 4 2 2 5 2 6 2 7 2 8 9 2 10 2 2 11 12 2 2 13 14 2 2 15 2 16 17 2 2 18 19 2 20 2 2 21 22 2 2 23 24 2 2 25 26 2 2 27 2 28 29 2 30 2 2 31 2 32 2 33 2 34 35 2 36 2 37 2 38 2 2 39 40 2 2 41 42 2 43 2 2 44 45 2 46 2 2 47 2 48 2 49 50 2 51 2 2 52 2 53 54 2 55 2 56 2 57 2 2 58 2 59 60 2 61 2 2 ...
output:
1 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:
ok AC
Test #11:
score: 0
Accepted
time: 5ms
memory: 4624kb
input:
20000 1 13291 13291 19998 3314 13291 13291 3339 13291 10237 13244 13291 13291 3392 13291 4459 13291 17335 13291 10356 6124 13291 13291 4470 12896 13291 13291 12094 3309 13291 13319 13291 13291 15658 13291 2305 13291 13710 13291 16520 13291 16234 6697 13291 13291 6686 9187 13291 13291 43 13291 2764 1...
output:
1 1064 19998 1064 3314 1064 3339 1064 10237 1064 13244 1064 3392 1064 4459 1064 17335 1064 10356 1064 6124 1064 4470 1064 12896 1064 12094 1064 3309 1064 13319 1064 15658 1064 2305 1064 13710 1064 16520 1064 16234 1064 6697 1064 6686 1064 9187 1064 43 1064 2764 1064 9061 1064 8113 1064 8449 1064 330...
result:
ok AC
Test #12:
score: 0
Accepted
time: 5ms
memory: 4764kb
input:
20000 4030 5565 1206 5565 5565 8947 4887 5565 14605 5565 5565 2947 5565 9038 5565 5326 5565 9021 11087 5565 5565 19562 895 5565 14653 5565 5565 10803 5565 9750 5565 16331 4689 5565 14307 5565 11631 5565 5565 13244 10554 5565 8112 5565 5565 9394 5565 5945 15279 5565 5565 15512 1334 5565 5565 6025 556...
output:
4030 14227 1206 14227 8947 14227 4887 14227 14605 14227 2947 14227 9038 14227 5326 14227 9021 14227 11087 14227 19562 14227 895 14227 14653 14227 10803 14227 9750 14227 16331 14227 4689 14227 14307 14227 11631 14227 13244 14227 10554 14227 8112 14227 9394 14227 5945 14227 15279 14227 15512 14227 133...
result:
ok AC
Test #13:
score: 0
Accepted
time: 22ms
memory: 10492kb
input:
100000 1 2 3 1 1 4 5 1 1 6 1 7 1 8 1 9 10 1 1 11 1 12 13 1 1 14 1 15 16 1 17 1 18 1 1 19 1 20 1 21 1 22 1 23 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 1 32 33 1 34 1 35 1 36 1 37 1 1 38 1 39 1 40 1 41 1 42 43 1 1 44 45 1 1 46 1 47 48 1 49 1 1 50 51 1 52 1 53 1 54 1 1 55 56 1 57 1 58 1 59 1 60 1 1 61 1...
output:
2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31 100000 32 10000...
result:
ok AC
Test #14:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
5 2 1 3 2 4 3 5 4
output:
1 5 2 5 3 5 4 1
result:
ok AC
Test #15:
score: 0
Accepted
time: 27ms
memory: 10572kb
input:
100000 21871 1 13678 1 27196 1 70437 1 1 35891 1 43010 28018 1 1 64489 61157 1 1 35572 1 41613 1 73049 93865 1 83507 1 1 92127 86278 1 1 15004 1 44154 2005 1 1 94210 41410 1 1 5886 69836 1 1 24120 1 80802 1 9940 66220 1 66549 1 1 20103 1 5 1 33021 35482 1 76185 1 34850 1 1 55173 1 72488 1 76286 1 99...
output:
21871 63055 13678 63055 27196 63055 70437 63055 35891 63055 43010 63055 28018 63055 64489 63055 61157 63055 35572 63055 41613 63055 73049 63055 93865 63055 83507 63055 92127 63055 86278 63055 15004 63055 44154 63055 2005 63055 94210 63055 41410 63055 5886 63055 69836 63055 24120 63055 80802 63055 99...
result:
ok AC
Test #16:
score: 0
Accepted
time: 28ms
memory: 10576kb
input:
100000 1 12976 28108 1 87682 1 79359 1 16128 1 1 90652 1 55874 27276 1 1 66899 1 10296 1 37870 1 78978 26221 1 28589 1 1 46430 32252 1 22407 1 68230 1 64944 1 1 53457 31023 1 1 57101 1 82578 1 33273 69683 1 64357 1 1 32517 1 45623 1 29497 41082 1 1 43731 1 28620 1 64304 1 23462 1 81982 1 91877 1 309...
output:
12976 78172 28108 78172 87682 78172 79359 78172 16128 78172 90652 78172 55874 78172 27276 78172 66899 78172 10296 78172 37870 78172 78978 78172 26221 78172 28589 78172 46430 78172 32252 78172 22407 78172 68230 78172 64944 78172 53457 78172 31023 78172 57101 78172 82578 78172 33273 78172 69683 78172 ...
result:
ok AC
Test #17:
score: 0
Accepted
time: 22ms
memory: 10564kb
input:
100000 1 2 2 3 4 2 5 2 2 6 7 2 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 16 2 2 17 18 2 19 2 20 2 21 2 2 22 23 2 24 2 2 25 2 26 27 2 28 2 29 2 30 2 2 31 32 2 2 33 34 2 35 2 2 36 2 37 38 2 2 39 40 2 2 41 42 2 43 2 44 2 45 2 2 46 47 2 2 48 49 2 50 2 2 51 2 52 2 53 2 54 2 55 56 2 2 57 58 2 59 2 60 2 61 2 6...
output:
1 99999 3 99999 4 99999 5 99999 6 99999 7 99999 8 99999 9 99999 10 99999 11 99999 12 99999 13 99999 14 99999 15 99999 16 99999 17 99999 18 99999 19 99999 20 99999 21 99999 22 99999 23 99999 24 99999 25 99999 26 99999 27 99999 28 99999 29 99999 30 99999 31 99999 32 99999 33 99999 34 99999 35 99999 36...
result:
ok AC
Test #18:
score: 0
Accepted
time: 21ms
memory: 10528kb
input:
100000 15924 1 13919 15924 86413 15924 15924 78418 36904 15924 15924 60478 15924 78563 15924 23855 63531 15924 15574 15924 73713 15924 62532 15924 15924 19461 15924 80750 15924 57012 15924 27046 55780 15924 69619 15924 58970 15924 65824 15924 15924 3195 26782 15924 71411 15924 84915 15924 95347 1592...
output:
1 26907 13919 26907 86413 26907 78418 26907 36904 26907 60478 26907 78563 26907 23855 26907 63531 26907 15574 26907 73713 26907 62532 26907 19461 26907 80750 26907 57012 26907 27046 26907 55780 26907 69619 26907 58970 26907 65824 26907 3195 26907 26782 26907 71411 26907 84915 26907 95347 26907 53739...
result:
ok AC
Test #19:
score: 0
Accepted
time: 28ms
memory: 10568kb
input:
100000 40659 47250 51514 40659 40659 83613 16333 40659 25291 40659 40659 61711 40659 37621 40659 66805 40659 59550 67744 40659 40659 46644 40659 21771 40659 98164 40659 6655 75053 40659 90431 40659 40659 58023 48769 40659 11506 40659 19125 40659 52852 40659 98702 40659 53360 40659 40659 3999 66767 4...
output:
47250 86919 51514 86919 83613 86919 16333 86919 25291 86919 61711 86919 37621 86919 66805 86919 59550 86919 67744 86919 46644 86919 21771 86919 98164 86919 6655 86919 75053 86919 90431 86919 58023 86919 48769 86919 11506 86919 19125 86919 52852 86919 98702 86919 53360 86919 3999 86919 66767 86919 82...
result:
ok AC
Test #20:
score: 0
Accepted
time: 6ms
memory: 4728kb
input:
20000 13211 1 1 10767 13211 16998 13211 495 10767 7635 10767 6994 10669 16998 1369 16998 495 4745 722 495 7635 251 3552 7635 7267 6994 6994 1772 10669 18929 10669 9328 3076 1369 1369 14212 4745 284 4745 9599 722 6137 722 10565 15137 251 5349 251 16431 3552 3552 15719 7267 10917 598 7267 19533 1772 1...
output:
1 10376 10767 10376 13211 10376 495 10376 7635 10376 6994 10376 10669 10376 16998 10376 4745 10376 722 10376 251 10376 3552 10376 7267 10376 1772 10376 18929 10376 9328 10376 3076 10376 1369 10376 284 10376 9599 10376 6137 10376 10565 10376 15137 10376 5349 10376 16431 10376 15719 10376 10917 10376 ...
result:
ok AC
Test #21:
score: 0
Accepted
time: 6ms
memory: 4628kb
input:
20000 11262 14400 16805 2790 19084 11979 15259 5949 9916 12236 2445 1637 1905 15141 9540 16655 12812 16186 19052 1523 6643 1443 13738 10091 9218 1337 16617 16436 17295 16466 1171 1217 19150 5280 2830 8076 16135 7234 11460 213 8101 341 5438 6331 5029 14871 10725 2090 5998 12241 8902 3420 4340 7265 18...
output:
14400 15050 16805 15050 11979 15050 5949 15050 9916 15050 2445 15050 15141 15050 16655 15050 16186 15050 1523 15050 1443 15050 10091 15050 9218 15050 16617 15050 16466 15050 1217 15050 19150 15050 2830 15050 7234 15050 11460 15050 8101 15050 6331 15050 14871 15050 10725 15050 12241 15050 8902 15050 ...
result:
ok AC
Test #22:
score: -100
Wrong Answer
time: 6ms
memory: 4748kb
input:
20000 19272 1 19272 7240 6952 7240 6952 10594 12564 10594 12564 13132 14483 13132 14483 1891 9772 1891 16614 9772 14519 16614 12050 14519 4039 12050 4039 9679 8408 4039 12050 6797 17990 6797 6797 17659 14519 14985 16415 14985 1735 16415 16415 18821 14985 9402 9402 18947 9402 5386 17560 16614 17560 1...
output:
19272 9518 7240 9518 6952 9518 10594 9518 12564 9518 13132 9518 14483 9518 1891 9518 9772 9518 16614 9518 14519 9518 12050 9518 4039 9518 9679 9518 8408 9518 6797 9518 17990 9518 17659 9518 14985 9518 16415 9518 1735 9518 18821 9518 9402 9518 18947 9518 5386 9518 17560 9518 1094 9518 7537 9518 19700...
result:
wrong answer u and v already exists