Submission #393570

#	Time	Username	Problem	Language	Result	Execution time	Memory
393570		tinjyu	Simurgh (IOI17_simurgh)	C++14	51 / 100	411 ms	4896 KiB

simurgh

#include "simurgh.h"
#include <iostream>
#include <vector>
using namespace std;
long long int val[100005],n,road[100005],map[1000005][2],m,cnt,tagv[1000005],tage[1000005],deg[100005],used[100005];
vector<int> r,r1;
int add(int a,int b)
{
	map[cnt][0]=b;
	map[cnt][1]=road[a];
	road[a]=cnt;
	cnt++;
	map[cnt][0]=a;
	map[cnt][1]=road[b];
	road[b]=cnt;
	cnt++;
	return 0;
}
long long int dfs(int x,int y)
{
	//cout<<x<<endl;
	tagv[x]=1;
	long long int g=road[x];
	while(g!=-1)
	{
		long long int now=map[g][0];
		//cout<<x<<" "<<now<<" "<<g<<endl;
		if(used[g/2]==0 && tagv[now]==0 && tage[g/2]==0)
		{
			used[g/2]=1;
			if(now==y)
			{
				r.push_back(g/2);
				return 0;
			}
			int tmp=dfs(now,y);
			if(tmp==0)
			{
				r.push_back(g/2);
				return 0;
			}
			used[g/2]=0;
		}
		g=map[g][1];
	}
	g=road[x];
	while(g!=-1)
	{
		long long int now=map[g][0];
		//cout<<x<<" "<<now<<" "<<g<<endl;
		if(used[g/2]==0 && tagv[now]==0 && tage[g/2]==1)
		{
			used[g/2]=1;
			if(now==y)
			{
				r.push_back(g/2);
				return 0;
			}
			int tmp=dfs(now,y);
			if(tmp==0)
			{
				r.push_back(g/2);
				return 0;
			}
			used[g/2]=0;
		}
		g=map[g][1];
	}
	return 1;
}
int dfs1(int x)
{
	tagv[x]=1;
	long long int g=road[x];
	while(g!=-1)
	{
		long long int now=map[g][0];
		if(tagv[now]==0)
		{
			r1.push_back(g/2);
			dfs1(now);
		}
		g=map[g][1];
	}
	return 0;
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	n=N;
	for(int i=0;i<n;i++)road[i]=-1;
	m=u.size();
	for(int i=0;i<m;i++)
	{
		add(u[i],v[i]);
		//cout<<u[i]<<" "<<v[i]<<" "<<map[i*2][0]<<" "<<map[i*2+1][0]<<endl;
	}
	vector<int> ans;
	vector<int> ask;
	for(int t=0;t<n;t++)
	{
		//cout<<i<<endl;
		long long int g=road[t];
		while(g!=-1)
		{
			long long int now=map[g][0];
			if(tage[g/2]==0)
			{
				for(int j=0;j<m;j++)used[j]=0;
				//cout<<t<<" "<<g/2<<endl;
				for(int j=0;j<n;j++)
				{
					tagv[j]=0;
				}
				r.clear();
				r1.clear();
				ask.clear();
				used[g/2]=1;
				long long int tmp=dfs(now,t);
				//for(int i=0;i<r.size();i++)cout<<r[i]<<" ";
				//cout<<endl;
				if(r.size()==0)
				{
					ans.push_back(g/2);
					tage[g/2]=1;
				}
				else
				{
					r.push_back(g/2);
					for(int i=0;i<n;i++)tagv[i]=0;
					for(int i=0;i<r.size();i++)
					{
						//cout<<r[i]<<" "<<u[r[i]]<<" "<<v[r[i]]<<endl;
						tagv[u[r[i]]]=1;
						tagv[v[r[i]]]=1;
					}
					for(int i=0;i<r.size();i++)
					{
						dfs1(u[r[i]]);
						//cout<<"ok"<<endl;
						dfs1(v[r[i]]);
					}
					long long int mi=9999999;
					long long int c=0;
					for(int i=0;i<r.size();i++)
					{
						ask.clear();
						for(int j=0;j<r.size();j++)
						{
							if(i==j)continue;
							ask.push_back(r[j]);
						}
						for(int j=0;j<r1.size();j++)
						{
							ask.push_back(r1[j]);
						}
						//cout<<"ask"<<endl;
						//for(int j=0;j<ask.size();j++)cout<<ask[j]<<" ";
						//cout<<endl; 
						val[i]=count_common_roads(ask);
						//cout<<val[i]<<endl;0
						mi=min(mi,val[i]);
					}
					for(int i=0;i<r.size();i++)
					{
						if(val[i]!=mi)c=1;
					}
					if(c==1)
					{
						for(int i=0;i<r.size();i++)
						{
							if(val[i]==mi)
							{
									if(tage[r[i]]==0)ans.push_back(r[i]);
							}
							
						}
					}
					for(int i=0;i<r.size();i++)tage[r[i]]=1;
				}
			}
			g=map[g][1];
		}
	}
	//cout<<"ans"<<endl;
	//for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
	//cout<<endl; 
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:129:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |      for(int i=0;i<r.size();i++)
      |                  ~^~~~~~~~~
simurgh.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |      for(int i=0;i<r.size();i++)
      |                  ~^~~~~~~~~
simurgh.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |      for(int i=0;i<r.size();i++)
      |                  ~^~~~~~~~~
simurgh.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |       for(int j=0;j<r.size();j++)
      |                   ~^~~~~~~~~
simurgh.cpp:151:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |       for(int j=0;j<r1.size();j++)
      |                   ~^~~~~~~~~~
simurgh.cpp:162:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |      for(int i=0;i<r.size();i++)
      |                  ~^~~~~~~~~
simurgh.cpp:168:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |       for(int i=0;i<r.size();i++)
      |                   ~^~~~~~~~~
simurgh.cpp:177:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |      for(int i=0;i<r.size();i++)tage[r[i]]=1;
      |                  ~^~~~~~~~~
simurgh.cpp:117:19: warning: unused variable 'tmp' [-Wunused-variable]
  117 |     long long int tmp=dfs(now,t);
      |                   ^~~

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