QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#720890 | #5545. Contingency Plan | subarudesu# | WA | 1ms | 3592kb | C++14 | 1.2kb | 2024-11-07 14:36:41 | 2024-11-07 14:36:42 |
Judging History
answer
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],p[N],s1[N],s2[N],d[N];
int head[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){
ver[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
void dfs(int x,int fa){
p[x]=fa;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa)continue;
s2[x]=s1[x];
s1[x]=y;
dfs(y,x);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;++i){
cin>>a[i]>>b[i];
d[a[i]]++;d[b[i]]++;
add(a[i],b[i]);
add(b[i],a[i]);
}
for(int i=1;i<=n;++i){
if(d[i]==n-1){
cout<<-1;
return 0;
}
}
dfs(1,0);
for(int i=1;i<n;++i){
if(p[a[i]]==b[i]){
swap(a[i],b[i]);
}
if(p[a[i]]){
cout<<p[a[i]]<<" "<<b[i]<<"\n";
}
else if(b[i]!=s1[a[i]]){
cout<<s1[a[i]]<<" "<<b[i]<<"\n";
}
else if(s2[a[i]]&&b[i]!=s2[a[i]]){
cout<<s2[a[i]]<<" "<<b[i]<<"\n";
}
else if(s1[b[i]]){
cout<<a[i]<<" "<<s1[b[i]]<<"\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3592kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
3 2 1 7 1 4 1 5 2 3 1 6
result:
wrong answer cycle detected