QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234799 | #5545. Contingency Plan | dmmm# | WA | 41ms | 14188kb | C++14 | 1.7kb | 2023-11-01 22:38:26 | 2023-11-01 22:38:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxN = 1e5 + 69;
struct vl {
int x, y;
size_t operator() (const vl& p) const {
return (p.x << 32) ^ p.y;
}
bool operator == (const vl& oth) const {
return x == oth.x && y == oth.y;
}
};
int n;
int u[maxN], v[maxN];
unordered_set<vl, vl> us;
set<int> adj[maxN];
mt19937 rng(time(NULL));
void dfs(int u, int p, vector<int>& res, int& cnt) {
res.push_back(u);
cnt--;
if (cnt <= 0) return;
for (int v : adj[u])
if (v != p) {
dfs(v, u, res, cnt);
if (cnt <= 0) return;
}
}
vector<int> getsome(int u) {
int cnt = 50;
vector<int> res;
dfs(u, u, res, cnt);
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
us.reserve(maxN * 2);
for (int i = 1; i <= n - 1; i++) {
cin >> u[i] >> v[i];
adj[u[i]].insert(v[i]);
adj[v[i]].insert(u[i]);
us.insert({min(u[i], v[i]), max(u[i], v[i])});
}
vector<int> ans;
for (int i = 1; i <= n - 1; i++) {
if (adj[u[i]].size() <= 1 && adj[v[i]].size() <= 1)
return cout << -1, 0;
adj[u[i]].erase(v[i]);
adj[v[i]].erase(u[i]);
vector<int> lolu = getsome(u[i]);
vector<int> lolv = getsome(v[i]);
shuffle(lolu.begin(), lolu.end(), rng);
shuffle(lolv.begin(), lolv.end(), rng);
int xu = -1, xv;
for (int yu : lolu)
for (int yv : lolv)
if (!us.count({min(yu, yv), max(yu, yv)})) {
xu = yu;
xv = yv;
goto flag;
}
flag:;
if (xu == -1) {
return cout << -1, 0;
}
adj[xu].insert(xv);
adj[xv].insert(xu);
ans.push_back(xu);
ans.push_back(xv);
// cout << xu << ' ' << xv << '\n';
}
for (int i = 0; i < ans.size(); i += 2)
cout << ans[i] << ' ' << ans[i + 1] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9556kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
3 2 2 7 7 4 4 5 1 4 5 6
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 9564kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 3ms
memory: 10956kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 10152kb
input:
5 2 1 2 3 2 4 4 5
output:
3 1 4 1 2 5 3 5
result:
ok AC
Test #5:
score: 0
Accepted
time: 3ms
memory: 9888kb
input:
5 1 4 3 4 4 5 2 5
output:
1 3 3 5 4 2 2 3
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 9524kb
input:
5 5 2 1 2 4 2 3 4
output:
5 1 1 4 3 2 3 1
result:
ok AC
Test #7:
score: 0
Accepted
time: 35ms
memory: 13228kb
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:
13 2 24 3 4 31 5 40 6 18 7 18 14 8 45 9 19 10 21 11 12 42 34 2 8 42 27 15 45 16 17 12 46 6 48 10 20 4 11 13 22 50 15 23 24 15 33 25 26 45 42 15 28 8 29 5 30 14 18 20 48 32 36 33 41 21 19 35 36 45 35 37 32 38 25 39 29 50 34 19 18 24 39 43 44 25 51 26 4 41 29 47 7 78 49 9 57 29 59 51 52 40 53 66 54 73...
result:
ok AC
Test #8:
score: 0
Accepted
time: 36ms
memory: 14188kb
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 12 9205 22 5971 28 36 9886 13 18853 14108 7662 998 8 37 14958 7100 7662 14108 2670 32 18493 13838 9205 4644 8 2139 5 35 18540 32 14081 34 16836 35 9357 245 12 242 7 8 13472 242 1471 3792 7 2670 17875 13976 242 21 15085 17875 17283 15014 17875 17477 15 11578 13 18441 15085 19 14367 3018 7100 172...
result:
ok AC
Test #9:
score: -100
Wrong Answer
time: 41ms
memory: 13152kb
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:
-1
result:
wrong output format Unexpected end of file - int32 expected