QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234800 | #5545. Contingency Plan | dmmm# | WA | 46ms | 13880kb | C++14 | 1.7kb | 2023-11-01 22:39:16 | 2023-11-01 22:39:16 |
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 = 100;
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';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9644kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
1 5 1 7 1 4 2 6 4 6 3 5
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 9636kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 10428kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 10184kb
input:
5 2 1 2 3 2 4 4 5
output:
5 1 1 3 2 5 4 1
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 9672kb
input:
5 1 4 3 4 4 5 2 5
output:
1 2 3 1 4 2 1 5
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 10132kb
input:
5 5 2 1 2 4 2 3 4
output:
5 3 1 5 3 2 5 4
result:
ok AC
Test #7:
score: 0
Accepted
time: 46ms
memory: 13880kb
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:
76 2 56 3 4 10 5 39 6 34 7 69 31 8 32 9 18 10 74 11 12 64 10 13 14 19 78 15 18 16 17 85 8 10 75 19 20 41 21 96 22 76 70 23 24 93 37 25 26 61 93 27 28 95 29 3 30 66 11 13 65 9 53 33 14 34 22 35 36 63 92 37 83 38 73 39 40 81 20 62 31 42 99 43 44 36 93 45 46 56 97 47 48 89 49 63 20 50 11 51 52 25 33 57...
result:
ok AC
Test #8:
score: -100
Wrong Answer
time: 45ms
memory: 13564kb
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