oj.uz

Submission #413655

# Submission time Handle Problem Language Result Execution time Memory
413655 2021-05-29T08:12:54 Z Jasiekstrz Simurgh (IOI17_simurgh) C++17
0 / 100
 322 ms 4252 KB 
#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;
vector<pair<int,int>> edg;
vector<int> base_tree_edg;
bool vis_curr[N+10];
bool vis_curr_e[M+10];
bool vis_e[M+10];
bool vis_solve[N+10];
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;
}
bool dfs_cycle(int x,int bg,vector<int> &cycle,vector<int> &cycle_e)
{
	vis[x]=true;
	cycle.push_back(x);
	for(auto v:e[x])
	{
		if(v.fi==bg && cycle.size()>2)
		{
			cycle_e.push_back(v.se);
			return true;
		}
		if(vis[v.fi] || vis_e[v.se])
			continue;
		cycle_e.push_back(v.se);
		if(dfs_cycle(v.fi,bg,cycle,cycle_e))
			return true;
		cycle_e.pop_back();
	}
	cycle.pop_back();
	return false;
}
int dfs_path(int x,vector<int> &path,vector<int> &path_e)
{
	//cerr<<x<<"\n";
	vis[x]=true;
	path.push_back(x);
	for(auto v:e[x])
	{
		if(vis[v.fi] || (vis_solve[v.fi] && !vis_curr[v.fi]))
			continue;
		if(vis_curr[v.fi] && path.size()>1)
		{
			path_e.push_back(v.se);
			return v.fi;
		}
		else if(vis_curr[v.fi])
			continue;
		path_e.push_back(v.se);
		int en=dfs_path(v.fi,path,path_e);
		//cerr<<x<<" "<<v.fi<<" "<<en<<"\n";
		if(en!=-1)
			return en;
		path_e.pop_back();
	}
	path.pop_back();
	return -1;
}
void dfs_rest(int x,vector<int> &que)
{
	vis[x]=true;
	for(auto v:e[x])
	{
		if(!vis[v.fi])
		{
			que.push_back(v.se);
			dfs_rest(v.fi,que);
		}
	}
	return;
}
bool dfs_curr_rest(int x,int en,vector<int> &que)
{
	if(x==en)
		return true;
	vis[x]=true;
	for(auto v:e[x])
	{
		if(!vis[v.fi] && vis_curr_e[v.se])
		{
			que.push_back(v.se);
			if(dfs_curr_rest(v.fi,en,que))
				return true;
			que.pop_back();
		}
	}
	return false;
}
void add_full(vector<int> &cycle,vector<int> &cycle_e,int n)
{
	//for(auto v:cycle)
	//	cerr<<v<<" ";
	//cerr<<"\n";
	//for(auto v:cycle_e)
	//	cerr<<v<<" ";
	//cerr<<"\n\n";
	int mn=n-1;
	vector<int> g;
	vector<int> que;
	que.reserve(n-1);
	for(auto v:cycle_e)
	{
		que.clear();
		for(auto v2:cycle_e)
		{
			if(v2!=v)
				que.push_back(v2);
		}
		for(int i=0;i<n;i++)
			vis[i]=false;
		for(auto v2:cycle)
			vis[v2]=true;
		for(auto v2:cycle)
			dfs_rest(v2,que);
		int tmp=count_common_roads(que);
		if(tmp<mn)
		{
			mn=tmp;
			g.clear();
		}
		if(tmp==mn)
			g.push_back(v);
	}
	for(auto v:g)
		wyn[v]=true;
	for(size_t i=0;i<cycle_e.size()-1;i++)
	{
		//cerr<<cycle_e[i]<<"\n";
		base_tree_edg.push_back(cycle_e[i]);
	}
	return;
}
void add_path(int bg,int en,vector<int> &cycle,vector<int> &cycle_e,
		vector<int> &path,vector<int> &path_e,int n)
{
	int mn=n-1;
	vector<int> g;
	vector<int> que;
	vector<int> rst;
	que.reserve(n-1);
	for(int i=0;i<n;i++)
		vis[i]=false;
	dfs_curr_rest(bg,en,rst);
	//cerr<<bg<<" "<<en<<"\n";
	//for(auto v:path_e)
	//	cerr<<v<<" ";
	//cerr<<"\n";
	//for(auto v:rst)
	//	cerr<<v<<" ";
	//cerr<<"\n\n";
	for(auto v:path_e)
	{
		que.clear();
		for(auto v2:path_e)
		{
			if(v2!=v)
				que.push_back(v2);
		}
		for(auto v2:rst)
			que.push_back(v2);
		for(int i=0;i<n;i++)
			vis[i]=false;
		for(auto v2:que)
			vis[edg[v2].fi]=vis[edg[v2].se]=true;
		for(int i=0;i<n;i++)
		{
			if(vis[i])
				dfs_rest(i,que);
		}
		//for(auto v:que)
		//	cerr<<v<<" ";
		//cerr<<"\n";
		//cerr<<"xd\n";
		int tmp=count_common_roads(que);
		//cerr<<"xd1\n";
		if(tmp<mn)
		{
			mn=tmp;
			g.clear();
		}
		if(tmp==mn)
			g.push_back(v);
	}
	que.clear();
	for(auto v2:path_e)
		que.push_back(v2);
	for(size_t i=0;i<rst.size()-1;i++)
		que.push_back(rst[i]);
	for(int i=0;i<n;i++)
		vis[i]=false;
	for(auto v2:que)
		vis[edg[v2].fi]=vis[edg[v2].se]=true;
	for(int i=0;i<n;i++)
	{
		if(vis[i])
			dfs_rest(i,que);
	}
	int tmp=count_common_roads(que);
	if(tmp<mn || (tmp==mn && !wyn[rst.back()]))
		g.clear();
	for(auto v:g)
		wyn[v]=true;
	for(size_t i=0;i<path_e.size()-1;i++)
		base_tree_edg.push_back(path_e[i]);
	return;
}
void solve(int x,int n)
{
	if(vis_solve[x])
		return;
	//cerr<<x<<"\n";
	for(int i=0;i<n;i++)
		vis_curr[i]=false;
	for(size_t i=0;i<edg.size();i++)
		vis_curr_e[i]=false;
	vector<int> cycle,cycle_e;
	for(int i=0;i<n;i++)
		vis[i]=false;
	if(!dfs_cycle(x,x,cycle,cycle_e))
		return;
	add_full(cycle,cycle_e,n);
	for(auto v:cycle)
		vis_curr[v]=vis_solve[v]=true;
	for(auto v:cycle_e)
		vis_e[v]=vis_curr_e[v]=true;
	//for(auto v:cycle)
	//	cerr<<v<<" ";
	//cerr<<"\n";
	vector<int> path,path_e;
	while(true)
	{
		path.clear();
		path_e.clear();
		for(int i=0;i<n;i++)
			vis[i]=false;
		int bg,en;
		for(bg=0;bg<n;bg++)
		{
			if(!vis_curr[bg])
				continue;
			en=dfs_path(bg,path,path_e);
			if(en!=-1)
				break;
		}
		if(path.empty())
			break;
		add_path(bg,en,cycle,cycle_e,path,path_e,n);
		for(auto v:path)
			vis_curr[v]=vis_solve[v]=true;
		for(auto v:path_e)
			vis_e[v]=vis_curr_e[v]=true;
	}
	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(edg[v].fi)!=fnd(edg[v].se))
		{
			un(edg[v].fi,edg[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();
	edg.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);
		edg[i]={u[i],v[i]};
	}
	for(int i=0;i<n;i++)
		solve(i,n);
	for(int i=0;i<n;i++)
		fau[i]=i;
	for(auto vv:base_tree_edg)
		un(edg[vv].fi,edg[vv].se);
	for(int i=0;i<m;i++)
	{
		auto vv=edg[i];
		if(fnd(vv.fi)!=fnd(vv.se))
		{
			base_tree_edg.push_back(i);
			wyn[i]=true;
			un(vv.fi,vv.se);
		}
	}
	//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;
}

Compilation message

simurgh.cpp: In function 'void solve(int, int)':
simurgh.cpp:266:11: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
  266 |   add_path(bg,en,cycle,cycle_e,path,path_e,n);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Incorrect 1 ms 204 KB WA in grader: NO
11 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Incorrect 1 ms 204 KB WA in grader: NO
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Incorrect 1 ms 204 KB WA in grader: NO
11 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB correct
2 Correct 1 ms 204 KB correct
3 Incorrect 322 ms 4252 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Incorrect 1 ms 204 KB WA in grader: NO
11 Halted 0 ms 0 KB -