QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258233 | #5545. Contingency Plan | hank55663# | TL | 2ms | 6252kb | C++14 | 2.0kb | 2023-11-19 16:11:50 | 2023-11-19 16:11:51 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acos(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
vector<pii> v[100005];
int val[100005];
void dfs(int x,int f){
for(auto it:v[x]){
if(it.x!=f){
dfs(it.x,x);
val[it.y]=it.x;
}
}
}
void solve(int T){
int n;
scanf("%d",&n);
set<pii> s;
for(int i = 1;i<n;i++){
int x,y;
scanf("%d %d",&x,&y);
v[x].pb(mp(y,i));
v[y].pb(mp(x,i));
s.insert(mp(x,y));
s.insert(mp(y,x));
}
for(int i = 1;i<=n;i++){
if(v[i].size()==n-1){
printf("-1\n");
return;
}
}
for(int i = 1;i<=n;i++){
if(v[i].size()==1&&v[i][0].y!=1){
dfs(i,0);
vector<pii> ans;
for(int j = 1;j<n;j++){
if(val[j]!=v[i][0].x){
//printf("%d %d\n",i,val[j]);
ans.pb(mp(i,val[j]));
}
else{
for(int k=1;k<j;k++){
if(s.find(mp(val[k],val[j]))==s.end()){
ans.pb(mp(val[k],val[j]));
break;
}
}
//printf("%d %d\n",val[1],val[j]);
}
}
if(ans.size()==n-1){
for(auto it:ans){
printf("%d %d\n",it.x,it.y);
}
return ;
}
}
}
}
int main(){
int t=1;
//scanf("%d",&t);
for(int i = 1;i<=t;i++){
// cerr<<i<<endl;
solve(i);
}
}
/*
1227076727
1919786269
1261786217
1924134973
1051246577
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6252kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
4 1 4 7 7 2 4 5 4 3 4 6
result:
ok AC
Test #2:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
3 1 2 2 3
output:
-1
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 5912kb
input:
2 2 1
output:
-1
result:
ok AC
Test #4:
score: 0
Accepted
time: 2ms
memory: 5904kb
input:
5 2 1 2 3 2 4 4 5
output:
5 1 5 3 5 2 1 4
result:
ok AC
Test #5:
score: 0
Accepted
time: 1ms
memory: 6024kb
input:
5 1 4 3 4 4 5 2 5
output:
2 1 2 3 2 4 1 5
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 5948kb
input:
5 5 2 1 2 4 2 3 4
output:
3 5 3 1 3 2 5 4
result:
ok AC
Test #7:
score: -100
Time Limit Exceeded
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 ...