Submission #68688

#	Time	Username	Problem	Language	Result	Execution time	Memory
68688		zscoder	Simurgh (IOI17_simurgh)	C++17	100 / 100	276 ms	16592 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct edge
{
	int to, id;
	edge(int _to, int _id) : to(_to),id(_id){}
};

vector<edge> adj[555];
int timer;
int in[555];
int royal[555555];
int par[555];
int paredge[555];
bool vis[555];
int backedge[555];
int low[555];
vector<ii> T[555];
vector<int> S;

void prep(int u=0, int p=-1)
{
	in[u]=timer++; par[u]=p; vis[u]=1; low[u]=in[u];
	for(auto X:adj[u])
	{
		int v=X.to; int lab=X.id;
		if(v==p) continue;
		if(vis[v])
		{
			if(in[v]<low[u])
			{
				low[u]=in[v];
				backedge[u]=lab;
			}
		}
		else
		{
			S.pb(lab); paredge[v]=lab;
			//cerr<<"TREE EDGE "<<u<<' '<<v<<'\n'; 
			T[u].pb(mp(v,lab)); T[v].pb(mp(u,lab));
			prep(v,u);
			if(low[v]<low[u])
			{
				low[u]=low[v];
				backedge[u]=backedge[v];
			}
		}
	}
}

int query(int u, int v) //del edge u, add edge v
{
	vi V;
	for(int x:S)
	{
		if(x!=u) V.pb(x);
	}
	V.pb(v);
	/*
	cerr<<"QUERY\n";
	for(int v:V)
	{
		cerr<<v<<' ';
	}
	cerr<<'\n';
	*/
	return count_common_roads(V);
}
vector<ii> edges;

int ask_forest(vector<int> E)
{
	vi ex;
	for(int z:E)
	{
		ii x=edges[z];
		ex.pb(x.fi); ex.pb(x.se); 
	}
	queue<int> q;
	bitset<522> used; used.reset();
	for(int x:ex) used.set(x,1);
	for(int i=0;i<511;i++){if(used[i]) q.push(i);}
	int extra=0;
	vi vec=E;
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(ii X:T[u])
		{
			int v=X.fi; int lab=X.se;
			if(used[v]) continue;
			extra+=royal[lab]; vec.pb(lab);
			q.push(v); used.set(v,1);
		}
	}
	return count_common_roads(vec)-extra;
}

void solve(vi V, int cur)
{
	int n=V.size();
	if(n==1)
	{
		royal[V[0]]=1; return ;
	}
	vi L,R;
	for(int i=0;i<n/2;i++) L.pb(V[i]);
	for(int i=n/2;i<n;i++) R.pb(V[i]);
	int tmp = ask_forest(L);
	if(tmp>0) solve(L,tmp);
	if(cur-tmp>0) solve(R,cur-tmp);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) 
{
	vi ans; int m=u.size();
	for(int i=0;i<m;i++) 
	{
		edges.pb(mp(u[i],v[i]));
		adj[u[i]].pb(edge(v[i],i)); adj[v[i]].pb(edge(u[i],i));
	}
	for(int i=0;i<n;i++) backedge[i]=-1;
	prep();
	for(int i=0;i<m;i++) royal[i]=-1;
	int tree_common = count_common_roads(S);
	vi backedges;
	for(int i=0;i<n;i++)
	{
		if(backedge[i]!=-1)
		{
			int x=u[backedge[i]]; int y=v[backedge[i]];
			if(in[x]<in[y]) swap(x,y);
			//cerr<<"BACK EDGE "<<i<<' '<<x<<' '<<y<<'\n';
			//x is grandchild of y
			vi path;
			while(x!=y)
			{
				path.pb(paredge[x]); x=par[x];
			}
			int known=-1;
			for(int e:path)
			{
				if(royal[e]!=-1) 
				{
					known=e;
					break;
				}
			}
			if(known==-1) //if no known edge, do the entire cycle
			{
				vi arr(int(path.size()));
				
				int exnonzero=-1;
				for(int j=0;j<path.size();j++)
				{
					arr[j]=query(path[j],backedge[i])-tree_common;
					if(arr[j]!=0) exnonzero=j;
				}
				
				//all 0 => none of them is part of tree because it's a cycle
				if(exnonzero==-1)
				{
					for(int v:path) royal[v]=0;
					royal[backedge[i]]=0;
				}
				else
				{
					if(arr[exnonzero]==1) //meaning backedge[i] is good
					{
						royal[backedge[i]]=1;
						for(int i=0;i<path.size();i++)
						{
							if(arr[i]==1) royal[path[i]]=0;
							else royal[path[i]]=1;
						}
					}
					else
					{
						royal[backedge[i]]=0;
						for(int i=0;i<path.size();i++)
						{
							if(arr[i]==0) royal[path[i]]=0;
							else royal[path[i]]=1;
						}
					}
				}
				/*
				cerr<<"RESULT : \n";
				for(int v:path) cerr<<v<<' '<<royal[v]<<'\n';
				cerr<<backedge[i]<<' '<<royal[backedge[i]]<<'\n';
				cerr<<'\n';
				*/
			}
			else //known is a known tree edge
			{
				int v = query(known, backedge[i]) - tree_common;
				v+=royal[known]; royal[backedge[i]]=v;
				for(int e:path)
				{
					if(royal[e]==-1)
					{
						int val = tree_common-query(e,backedge[i]);
						val+=royal[backedge[i]];
						royal[e]=val;
					}
				}
				/*
				cerr<<"RESULT : \n";
				for(int v:path) cerr<<v<<' '<<royal[v]<<'\n';
				cerr<<backedge[i]<<' '<<royal[backedge[i]]<<'\n';
				cerr<<'\n';
				*/
			}
		}
	}
	for(int e:S)
	{
		if(royal[e]==-1) royal[e]=1; //because it is a bridge
	}
	//now we should have determined the affinity of all the tree edges
	//optimize this part to nlogn
	/*
	for(int i=0;i<m;i++)
	{
		if(royal[i]==-1)
		{
			int x=u[i]; int y=v[i];
			if(in[x]<in[y]) swap(x,y);
			//x is a grandchild of y
			int v = query(paredge[x], i) - tree_common;
			v+=royal[paredge[x]];
			royal[i]=v;
		}
	}
	*/
	for(int i=0;i<m;i++)
	{
		if(royal[i]==-1) royal[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		vi V;
		for(edge v:adj[i])
		{
			if(v.to>i) V.pb(v.id);
		}
		if(V.empty()) continue;
		int ans = ask_forest(V);
		if(ans>0) solve(V,ans);
	}
	for(int i=0;i<m;i++)
	{
		if(royal[i]) ans.pb(i);
	}
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:171:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<path.size();j++)
                 ~^~~~~~~~~~~~
simurgh.cpp:188:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path.size();i++)
                   ~^~~~~~~~~~~~
simurgh.cpp:197:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path.size();i++)
                   ~^~~~~~~~~~~~

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