QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#339307#5545. Contingency PlanAllSolvedin1557#WA 1ms3612kbC++203.3kb2024-02-26 23:58:282024-02-26 23:58:29

Judging History

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

  • [2024-02-26 23:58:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-02-26 23:58:28]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

vector<ll>v[100005];
ll pr[100005];
vector<ll>lfv;
void dfs(ll x,ll p)
{
    if(v[x].size()==1) lfv.push_back(x);
    pr[x]=p;
    for(auto i:v[x])
    {
        if(i==p) continue;
        dfs(i,x);
    }
}

pll er[100005];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    ll n,r;
    cin>>n;
    for(ll i=1;i<n;i++)
    {
        ll a,b;
        cin>>a>>b;
        er[i]={a,b};
        v[a].push_back(b); v[b].push_back(a);
    }
    if(n<=3) return cout<<"-1", 0;
    bool flag=0;
    for(ll i=1;i<=n;i++) if(v[i].size()==n-1) flag=1;
    if(flag) return cout<<"-1", 0;
    r=1;
    dfs(r,0);
    pll lf={-1,-1};
    for(ll i=0;i+1<lfv.size();i++)
        if(pr[lfv[i]]!=pr[lfv[i+1]]) lf={lfv[i],lfv[i+1]};
    ll pa=pr[lf.fi];
    if(er[1].fi==lf.fi||er[1].se==lf.fi)
    {
        cout<<lf.fi<<' '<<lf.se<<'\n';
        set<pll>path,pathb;
        ll x=lf.fi;
        while(x!=1)
        {
            path.insert({x,pr[x]});
            path.insert({pr[x],x});
            x=pr[x];
        }
        x=lf.se;
        while(x!=1)
        {
            pathb.insert({x,pr[x]});
            pathb.insert({pr[x],x});
            x=pr[x];
        }
        bool flag=0;
        for(ll i=2;i<n;i++)
        {
            if(er[i].fi==lf.se||er[i].se==lf.se)
            {
                cout<<lf.se<<' '<<pr[lf.fi]<<'\n';
                flag=1;
            }
            else if(path.count(er[i]))
            {
                if(pr[er[i].fi]==er[i].se) cout<<lf.fi<<' '<<er[i].se<<'\n';
                else cout<<lf.fi<<' '<<er[i].fi<<'\n';
            }
            else if(pathb.count(er[i]))
            {
                if(flag==1)
                {
                    if(pr[er[i].fi]==er[i].se) cout<<lf.fi<<' '<<er[i].se<<'\n';
                    else cout<<lf.fi<<' '<<er[i].fi<<'\n';
                }
                else
                {

                    if(pr[er[i].fi]==er[i].se) cout<<lf.fi<<' '<<er[i].fi<<'\n';
                    else cout<<lf.fi<<' '<<er[i].se<<'\n';
                }

            }
            else
            {
                if(pr[er[i].fi]==er[i].se) cout<<lf.fi<<' '<<er[i].fi<<'\n';
                else cout<<lf.fi<<' '<<er[i].se<<'\n';
            }
        }
    }
    else
    {
        set<pll>path;
        ll x=lf.fi;
        while(x!=1)
        {
            path.insert({x,pr[x]});
            path.insert({pr[x],x});
            x=pr[x];
        }
        for(ll i=1;i<n;i++)
        {
            if(er[i].fi==lf.fi||er[i].se==lf.fi)
            {
                cout<<pr[lf.fi]<<' '<<lf.se<<'\n';
            }
            else if(er[i].fi==lf.se||er[i].se==lf.se)
            {
                cout<<lf.se<<' '<<lf.fi<<'\n';
            }
            else if(path.count(er[i]))
            {
                if(pr[er[i].fi]==er[i].se) cout<<lf.fi<<' '<<er[i].se<<'\n';
                else cout<<lf.fi<<' '<<er[i].fi<<'\n';
            }
            else
            {
                if(pr[er[i].fi]==er[i].se) cout<<lf.fi<<' '<<er[i].fi<<'\n';
                else cout<<lf.fi<<' '<<er[i].se<<'\n';
            }
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

input:

7
1 2
3 7
2 4
2 5
1 3
3 6

output:

5 1
7 5
5 4
2 7
5 3
5 6

result:

ok AC

Test #2:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3596kb

input:

5
2 1
2 3
2 4
4 5

output:

3 1
2 5
3 4
5 3

result:

wrong answer cycle detected