QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234802 | #5545. Contingency Plan | dmmm# | WA | 127ms | 13352kb | C++14 | 1.7kb | 2023-11-01 22:40:12 | 2023-11-01 22:40:13 |
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 = 300;
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: 2ms
memory: 10208kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
3 2 6 7 7 4 1 5 1 4 3 4
result:
ok AC
Test #2:
score: 0
Accepted
time: 3ms
memory: 10724kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 2ms
memory: 10020kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 2ms
memory: 10964kb
input:
5 2 1 2 3 2 4 4 5
output:
3 1 4 3 2 5 1 5
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 9820kb
input:
5 1 4 3 4 4 5 2 5
output:
1 3 3 2 4 2 1 5
result:
ok AC
Test #6:
score: 0
Accepted
time: 2ms
memory: 9628kb
input:
5 5 2 1 2 4 2 3 4
output:
5 1 1 3 3 2 5 4
result:
ok AC
Test #7:
score: 0
Accepted
time: 127ms
memory: 13352kb
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:
230 2 16 3 4 289 5 187 6 194 7 264 162 8 71 9 59 10 179 11 12 162 205 13 14 138 251 15 234 3 17 163 197 18 119 19 20 244 21 231 22 107 108 23 24 100 78 25 26 41 94 27 28 207 29 237 30 21 140 31 175 32 47 33 217 34 252 35 36 129 190 37 69 38 86 39 40 298 26 270 268 42 300 43 44 234 78 45 46 204 30 33...
result:
ok AC
Test #8:
score: -100
Wrong Answer
time: 124ms
memory: 13316kb
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:
-1
result:
wrong output format Unexpected end of file - int32 expected