QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#339304	#5545. Contingency Plan	AllSolvedin1557^#	WA	1ms	3652kb	C++20	2.7kb	2024-02-26 23:45:58	2024-02-26 23:45:59

Judging History

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

[2024-02-26 23:45:59]
评测

测评结果：WA
用时：1ms
内存：3652kb

查看

[2024-02-26 23:45:58]
提交

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;
        ll x=lf.fi;
        while(x!=1)
        {
            path.insert({x,pr[x]});
            path.insert({pr[x],x});
            x=pr[x];
        }
        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';
            }
            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';
            }
        }
    }
    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;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3652kb

input:

output:

result:

ok AC

Test #2:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: -100

Wrong Answer

time: 1ms

memory: 3584kb

input:

output:

result:

wrong answer cycle detected