Submission #831761

#	Time	Username	Problem	Language	Result	Execution time	Memory
831761		Rafi22	Simurgh (IOI17_simurgh)	C++14	100 / 100	151 ms	6868 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;

const int N=507,M=507*507;

int U[M],V[M];
int n;

vector<pair<int,int>>G[N];
int odw[N],c;
int o[N],id[N];
vector<int>st;

int val[M];

void dfs(int v)
{
	odw[v]=++c;
	for(auto [u,i]:G[v])
	{
		if(!odw[u])
		{
			o[u]=v;
			id[u]=i;
			st.pb(i);
			dfs(u);
		}
	}
}

int get(int x)
{
	vector<int>Q;
	for(auto y:st) if(y!=x) Q.pb(y);
	return count_common_roads(Q);
}

void dfs1(int v)
{
	odw[v]=++c;
	for(auto [u,i]:G[v])
	{
		if(!odw[u]) dfs1(u);
		else if(odw[u]<odw[v]&&u!=o[v])
		{
			vector<int>X={i};
			st.pb(i);
			int p=-1,x=v;
			while(x!=u)
			{
				if(val[id[x]]) p=id[x];
				else X.pb(id[x]); 
				x=o[x];
			}
			if(sz(X)==1)
			{
				 st.pop_back();
				 continue;
			}
			if(p==-1)
			{
				vector<pair<int,int>>W;
				int mx=-inf;
				for(auto x:X) 
				{
					int k=get(x);
					mx=max(mx,k);
					W.pb({k,x});
				}
				for(auto [k,x]:W)
				{
					if(k<mx) val[x]=2;
					else val[x]=1;
				}
			}
			else 
			{
				for(auto x:X) 
				{
					int c1=get(p),c2=get(x);
					if(c1==c2) val[x]=val[p];
					else if(c1<c2) val[x]=1;
					else val[x]=2;
				}
			}
			st.pop_back();
		}
	}
	if(!val[id[v]]) val[id[v]]=2;
}

bool was[M];
vector<int>co[N];

int r[N];

int Find(int v)
{
	if(r[v]==v) return v;
	return r[v]=Find(r[v]);
}
void Union(int v,int u)
{
	u=Find(u),v=Find(v);
	r[u]=v;
}

int ile;

int qry(vector<int>W)
{
	vector<int>Q;
	for(int i=0;i<n;i++) r[i]=i;
	for(auto x:W) 
	{
		Union(U[x],V[x]);
		Q.pb(x);
	}
	int k=ile;
	for(auto x:st)
	{
		if(Find(U[x])==Find(V[x])) k-=val[x]-1;
		else 
		{
			Union(U[x],V[x]);
			Q.pb(x);
		}
 	}
 	return count_common_roads(Q)-k;
}

vector<int>find_roads(int nn,vector<int>uu,vector<int>vv)
{
	n=nn;
	int m=sz(uu);
	for(int i=0;i<m;i++) 
	{
		U[i]=uu[i];
		V[i]=vv[i];
		if(U[i]>V[i]) swap(U[i],V[i]);
		G[U[i]].pb({V[i],i});
		G[V[i]].pb({U[i],i});
	}
	dfs(0);
	memset(odw,0,sizeof odw);
	dfs1(0);
	for(auto x:st) was[x]=1;
	for(int i=0;i<m;i++)
	{
		if(!was[i]) co[U[i]].pb(i);
	}
	ile=count_common_roads(st);
	for(int i=0;i<n;i++)
	{
		vector<int>Q;
		for(auto x:co[i]) Q.pb(x);
		int deg=qry(Q);
		for(int j=1;j<=deg;j++)
		{
			int l=0,r=sz(co[i])-1,sr,p;
			while(l<=r)
			{
				sr=(l+r)/2;
				Q.clear();
				for(int k=0;k<=sr;k++) Q.pb(co[i][k]);
				if(qry(Q)>=j)
				{
					r=sr-1;
					p=sr;
				}
				else l=sr+1;
			}
			val[co[i][p]]=2;
		}
	}
	vector<int>ans;
	for(int i=0;i<m;i++) if(val[i]==2) ans.pb(i);
	return ans;
}
/*
int main()
{
	vector<int>X=find_roads(4,{0, 0, 0, 1, 1, 2},{1, 2, 3, 2, 3, 3});
	return 0;
}*/

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:31:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |  for(auto [u,i]:G[v])
      |           ^
simurgh.cpp: In function 'void dfs1(int)':
simurgh.cpp:53:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |  for(auto [u,i]:G[v])
      |           ^
simurgh.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for(auto [k,x]:W)
      |              ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:185:15: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  185 |    val[co[i][p]]=2;
      |               ^

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