QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234797 | #5545. Contingency Plan | dmmm# | WA | 23ms | 14188kb | C++14 | 1.7kb | 2023-11-01 22:36:53 | 2023-11-01 22:36:54 |
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 = 30;
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: 9820kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
1 5 4 7 3 4 2 3 5 3 7 6
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 9820kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 10208kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 2ms
memory: 9660kb
input:
5 2 1 2 3 2 4 4 5
output:
4 1 1 3 2 5 1 5
result:
ok AC
Test #5:
score: 0
Accepted
time: 2ms
memory: 11044kb
input:
5 1 4 3 4 4 5 2 5
output:
1 5 3 1 4 2 2 3
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 9856kb
input:
5 5 2 1 2 4 2 3 4
output:
5 4 1 3 3 2 3 5
result:
ok AC
Test #7:
score: -100
Wrong Answer
time: 23ms
memory: 14188kb
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:
-1
result:
wrong output format Unexpected end of file - int32 expected