QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720890#5545. Contingency Plansubarudesu#WA 1ms3592kbC++141.2kb2024-11-07 14:36:412024-11-07 14:36:42

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 14:36:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3592kb
  • [2024-11-07 14:36:41]
  • 提交

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;
}

詳細信息

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