QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#255501 | #5545. Contingency Plan | sentheta# | WA | 3ms | 8252kb | C++20 | 2.2kb | 2023-11-18 16:08:03 | 2023-11-18 16:08:03 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define int long long
#define pii pair<int,int>
#define pb emplace_back
#define rep(i,a,b) for(int i=a; i < b; ++i)
#define owo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define V vector
#define cerr if(1) cout
#define dbg(x) cerr << "?" << #x << " : " << x << endl;
void solve();
signed main(){
owo
int t = 1; //cin >> t
while(t--) solve();
}
const int N = 1e5+5;
int n;
array<int,2> edg[N];
V<int> adj[N];
int r[4];
int d[N], p[N];
void dfs(int x,int par){
for(int e : adj[x]){
int y = edg[e][0]^edg[e][1]^x;
if(y==par) continue;
bool isr = 0;
rep(i,0,4){
isr |= y==r[i];
}
if(isr) continue;
p[y] = p[x];
d[y] = d[x]+1;
dfs(y, x);
}
}
bool g[4][4], gvis[4];
int gdfs(int x){
if(gvis[x]) return 0;
gvis[x] = 1;
int ret = 1;
rep(y,0,4) if(g[x][y]){
ret += gdfs(y);
}
return ret;
}
void solve(){
cin >> n;
rep(e,1,n){
int u, v;
cin >> u >> v;
edg[e] = {u,v};
adj[u].push_back(e);
adj[v].push_back(e);
}
r[1] = -1;
rep(e,1,n){
auto[u,v] = edg[e];
if(adj[u].size()>=2 && adj[v].size()>=2){
r[1] = u; r[2] = v; break;
}
}
if(r[1]==-1){
cout << -1 << '\n'; return;
}
for(int e : adj[r[1]]){
int x = edg[e][0]^edg[e][1]^r[1];
if(x!=r[2]){
r[0] = x; break;
}
}
for(int e : adj[r[2]]){
int x = edg[e][0]^edg[e][1]^r[2];
if(x!=r[1]){
r[3] = x; break;
}
}
rep(i,0,4){
// dbg(r[i]);
p[r[i]] = i;
dfs(r[i], r[i]);
}
g[0][1] = g[1][2] = g[2][3] = 1;
g[3][2] = g[2][1] = g[1][0] = 1;
rep(e,1,n){
auto[u,v] = edg[e];
if(d[u]==0 && d[v]==0){
int i = p[u], j = p[v];
g[i][j] = g[j][i] = 0;
bool found = 0;
rep(ii,0,4) if(!found) rep(jj,0,ii-1) if(!found)
if(!g[ii][jj]){
g[ii][jj] = g[jj][ii] = 1;
gvis[0] = gvis[1] = gvis[2] = gvis[3] = 0;
if(gdfs(r[0])==4){
found = 1;
cout << r[ii] << " " << r[jj] << "\n";
}
else{
g[ii][jj] = g[jj][ii] = 0;
}
}
}
else{
if(!(d[u]<d[v])) swap(u,v);
cout << v << " " << r[(p[v]+1)%4] << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7680kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
2 3 7 1 4 3 5 4 4 1 6 1
result:
ok AC
Test #2:
score: 0
Accepted
time: 1ms
memory: 7436kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 7432kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 7620kb
input:
5 2 1 2 3 2 4 4 5
output:
4 1 3 4 5 2 5 1
result:
ok AC
Test #5:
score: 0
Accepted
time: 1ms
memory: 7504kb
input:
5 1 4 3 4 4 5 2 5
output:
5 1 3 5 2 4 2 1
result:
ok AC
Test #6:
score: 0
Accepted
time: 1ms
memory: 7660kb
input:
5 5 2 1 2 4 2 3 4
output:
5 3 1 5 2 3 5 4
result:
ok AC
Test #7:
score: 0
Accepted
time: 3ms
memory: 7000kb
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:
19999 2 3 19999 4 19999 5 19999 6 19999 7 19999 8 19999 9 19999 10 19999 11 19999 12 19999 13 19999 14 19999 15 19999 16 19999 17 19999 18 19999 19 19999 20 19999 21 19999 22 19999 23 19999 24 19999 25 19999 26 19999 27 19999 28 19999 29 19999 30 19999 31 19999 32 19999 33 19999 34 19999 35 19999 36...
result:
ok AC
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 8252kb
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:
9205 7662 5971 7662 9886 7662 18853 7662 14108 7662 998 7662 14958 7662 7100 7662 2670 7662 18493 7662 13838 7662 4644 7662 2139 7662 18540 7662 14081 7662 16836 7662 9357 7662 245 7662 242 7662 13472 7662 1471 7662 3792 7662 17875 7662 13976 7662 15085 7662 17283 7662 15014 7662 17477 7662 11578 76...
result:
wrong output format Unexpected end of file - int32 expected