Submission #413387

#	Time	Username	Problem	Language	Result	Execution time	Memory
413387		Jasiekstrz	Simurgh (IOI17_simurgh)	C++17	19 / 100	433 ms	6760 KiB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"
#define fi first
#define se second
using namespace std;
const int N=500;
const int M=N*N;
vector<pair<int,int>> e[N+10];
vector<int> ans;
bool wyn[M+10];
bool vis[N+10];
vector<int> alw;
bool vis_solve[N+10];
vector<pair<int,int>> edges;
vector<int> base_tree_edg;
int fau[N+10];
int fnd(int x)
{
	if(fau[x]!=x)
		fau[x]=fnd(fau[x]);
	return fau[x];
}
void un(int x,int y)
{
	fau[fnd(x)]=fnd(y);
	return;
}
void dfs(int x,int r,vector<pair<int,int>> &vec)
{
	//cerr<<x<<" "<<r<<"\n";
	vis[x]=true;
	for(auto v:e[x])
	{
		if(vis[v.fi])
			continue;
		else if(v.fi==r)
			vec.emplace_back(x,v.se);
		else
		{
			alw.push_back(v.se);
			dfs(v.fi,r,vec);
		}
	}
	return;
}
int ask(vector<int> &my)
{
	for(auto v:my)
		alw.push_back(v);
	int tmp=count_common_roads(alw);
	for(size_t i=0;i<my.size();i++)
		alw.pop_back();
	return tmp;
}
void solve(int x,int n)
{
	for(int i=0;i<n;i++)
		vis[i]=false;
	alw.clear();
	vector<vector<pair<int,int>>> vec;
	for(int i=0;i<n;i++)
	{
		if(i==x || vis[i])
			continue;
		vec.push_back({});
		dfs(i,x,vec.back());
	}
	vector<int> my(vec.size());
	for(size_t i=0;i<vec.size();i++)
		my[i]=vec[i][0].se;	
	vector<int> g;
	for(size_t i=0;i<vec.size();i++)
	{
		int mx=0;
		g.clear();
		bool chck=false;
		for(auto v:vec[i])
		{
			//cerr<<x<<" "<<i<<" "<<v.fi<<"\n";
			if(vis_solve[v.fi] && (chck || !wyn[v.se] || vec[i].size()==1))
				continue;
			else if(vis_solve[v.fi])
				chck=true;
			my[i]=v.se;
			int tmp=ask(my);
			//cerr<<tmp<<" "<<mx<<"\n";
			if(tmp>mx)
			{
				mx=tmp;
				g.clear();
			}
			if(tmp==mx && !vis_solve[v.fi])
				g.push_back(v.se);
		}
		for(auto v:g)
		{
			wyn[v]=true;
			//cerr<<"wyn "<<x<<" "<<i<<" "<<v<<"\n";
		}
	}
	return;
}
void dfs_solve(int x,int n)
{
	//cerr<<x<<"\n";
	solve(x,n);
	vector<int> tmp_e;
	for(auto v:e[x])
	{
		if(!vis_solve[v.fi])
		{
			//cerr<<x<<" "<<v.fi<<"\n";
			vis_solve[v.fi]=true;
			base_tree_edg.push_back(v.se);
			tmp_e.push_back(v.fi);
		}
	}
	for(auto v:tmp_e)
		dfs_solve(v,n);
	return;
}
int ask_interval(int x,int l,int r,int n)
{
	int tmp_s=0;
	vector<int> tmp;
	tmp.reserve(n-1);
	for(int i=0;i<n;i++)
		fau[i]=i;
	for(auto v:e[x])
	{
		if(l<=v.fi && v.fi<=r)
		{
			tmp.push_back(v.se);
			un(v.fi,x);
		}
	}
	for(auto v:base_tree_edg)
	{
		if(fnd(edges[v].fi)!=fnd(edges[v].se))
		{
			un(edges[v].fi,edges[v].se);
			tmp.push_back(v);
			tmp_s-=wyn[v];
		}
	}
	return tmp_s+count_common_roads(tmp);
}
void bs(int x,int l,int r,int s,int n)
{
	if(s==0)
		return;
	if(l==r)
	{
		for(auto v:e[x])
		{
			if(v.fi==l)
			{
				wyn[v.se]=true;
				break;
			}
		}
		return;
	}
	int mid=(l+r)/2;
	int tmp_s=ask_interval(x,l,mid,n);
	bs(x,l,mid,tmp_s,n);
	bs(x,mid+1,r,s-tmp_s,n);
	return;
}
vector<int> find_roads(int n,vector<int> u,vector<int> v)
{
	int m=u.size();
	edges.resize(m);
	for(int i=0;i<m;i++)
	{
		e[u[i]].emplace_back(v[i],i);
		e[v[i]].emplace_back(u[i],i);
		edges[i]={u[i],v[i]};
	}
	vis_solve[0]=true;
	dfs_solve(0,n);
	//for(auto v:base_tree_edg)
	//	cerr<<v<<" "<<wyn[v]<<"\n";
	for(int i=0;i<n;i++)
		bs(i,0,i-1,ask_interval(i,0,i-1,n),n);
	for(int i=0;i<m;i++)
	{
		if(wyn[i])
		{
			ans.push_back(i);
			//cerr<<i<<"\n";
		}
	}
	return ans;
}

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