Submission #136567

#	Time	Username	Problem	Language	Result	Execution time	Memory
136567		baluteshih	Simurgh (IOI17_simurgh)	C++14	100 / 100	613 ms	5624 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define MP make_pair
#define F first
#define S second
using namespace std;
typedef pair<int,int> pii;

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()
{
	return count_common_roads(vector<int>(s.begin(),s.end()));
}

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),fill(type,type+N,-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&&!~tp)
				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 (stderr)

simurgh.cpp: In function 'int leaf_finding(int)':
simurgh.cpp:71: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:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();++i)
              ~^~~~~~~~~
simurgh.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();++i)
              ~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30