QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#339308 | #5545. Contingency Plan | AllSolvedin1557# | WA | 1ms | 3488kb | C++20 | 4.0kb | 2024-02-26 23:59:07 | 2024-02-26 23:59:07 |
Judging History
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,pathb;
bool flag=0;
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];
}
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';
flag=1;
}
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(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';
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3488kb
input:
7 1 2 3 7 2 4 2 5 1 3 3 6
output:
5 1 7 5 5 4 2 7 5 1 5 6
result:
wrong answer u and v already exists