#include "simurgh.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector<int> U,V;
vector<pii> G[505];
pii pa[505];
queue<int> q;
int type[505],dep[505],deg[505],boss[505],n;
set<int> s;
bitset<505> vis,ed;
bitset<250000> used;
int ccr()
{
vector<int> r;
for(auto i:s)
r.pb(i);
return count_common_roads(r);
}
void dfs(int u,int f,int num,int d)
{
pa[u]=MP(f,num),dep[u]=d,vis[u]=1;
if(~num) used[num]=1,s.insert(num);
for(pii i:G[u])
if(!vis[i.F])
dfs(i.F,u,i.S,d+1);
}
int finds(int x)
{
if(x==boss[x]) return x;
return boss[x]=finds(boss[x]);
}
int Union(int a,int b)
{
a=finds(a),b=finds(b);
if(a==b) return 0;
return boss[a]=b,1;
}
int ccr_forest(vector<int> f)
{
int cnt=0;
for(int i=0;i<n;++i)
boss[i]=i;
set<int> tmp;
for(int i:f)
tmp.insert(i),Union(U[i],V[i]);
for(int i=1;i<n;++i)
if(Union(i,pa[i].F))
cnt+=type[i],tmp.insert(pa[i].S);
tmp.swap(s);
cnt=ccr()-cnt;
tmp.swap(s);
return cnt;
}
int leaf_finding(int u)
{
vector<int> candi;
for(pii i:G[u])
if(!ed[i.F])
candi.pb(i.S);
int l=0,r=candi.size()-1;
while(l<r)
{
vector<int> v;
int m=l+r>>1;
for(int i=l;i<=m;++i)
v.pb(candi[i]);
if(ccr_forest(v)>=1) r=m;
else l=m+1;
}
return candi[l];
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
n=N,U=u,V=v;
vector<int> ans;
for(int i=0;i<u.size();++i)
G[u[i]].pb(MP(v[i],i)),G[v[i]].pb(MP(u[i],i));
dfs(0,-1,-1,0),MEM(type,-1);
int cur=ccr();
for(int i=0;i<u.size();++i)
{
if(used[i]) continue;
int cnt=0,sz=0,tp=-1,a=u[i],b=v[i];
pii sw;
while(a!=b)
{
if(dep[a]<dep[b]) swap(a,b);
if(~type[a]) sw=MP(pa[a].S,type[a]);
cnt+=!~type[a],++sz,a=pa[a].F;
}
if(!cnt) continue;
a=u[i],b=v[i];
if(cnt==sz)
{
vector<int> v;
while(a!=b)
{
if(dep[a]<dep[b]) swap(a,b);
s.erase(pa[a].S),s.insert(i);
int tmp=ccr();
if(tmp==cur) v.pb(a);
else
{
if(tmp>cur) tp=1,type[a]=0;
else tp=0,type[a]=1;
for(int j:v)
type[j]=tp;
s.erase(i),s.insert(pa[a].S),a=pa[a].F;
break;
}
s.erase(i),s.insert(pa[a].S),a=pa[a].F;
}
if(a==b)
for(int j:V)
type[j]=0;
}
else
{
s.erase(sw.F),s.insert(i);
tp=(sw.S==0)^(ccr()==cur);
s.erase(i),s.insert(sw.F);
}
while(a!=b)
{
if(dep[a]<dep[b]) swap(a,b);
s.erase(pa[a].S),s.insert(i);
if(!~type[a])
type[a]=tp^(ccr()!=cur);
s.erase(i),s.insert(pa[a].S),a=pa[a].F;
}
}
for(int i=1;i<n;++i)
if(!~type[i]) type[i]=1;
for(int i=0;i<n;++i)
{
vector<int> v;
for(pii j:G[i])
v.pb(j.S);
deg[i]=ccr_forest(v);
if(deg[i]==1)
q.push(i);
}
while(q.size()>1)
{
int u=q.front();
q.pop(),ed[u]=1;
ans.pb(leaf_finding(u));
u^=U[ans.back()]^V[ans.back()];
if(--deg[u]==1)
q.push(u);
}
return ans;
}
Compilation message
simurgh.cpp: In function 'int leaf_finding(int)':
simurgh.cpp:83:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:96:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();++i)
~^~~~~~~~~
simurgh.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<u.size();++i)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
376 KB |
correct |
| 3 |
Correct |
343 ms |
4068 KB |
correct |
| 4 |
Incorrect |
534 ms |
5588 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
