Submission #117296

#	Time	Username	Problem	Language	Result	Execution time	Memory
117296		tinjyu	Simurgh (IOI17_simurgh)	C++14	0 / 100	2 ms	384 KiB

simurgh

#include "simurgh.h"
#include <iostream>
using namespace std;
long long int can,n,tag[505],map[505][505],m,r,road[505],tmpans[505][505],s1,s2,anstag[250000];
int bfs(int x,int end,int p)
{
	for(int i=0;i<n;i++)
	{
		if(map[i][x]!=-1 && tag[i]==0 && map[i][x]!=s1 && map[i][x]!=s2)
		{
			tag[i]=1;
			road[p]=map[i][x];
			if(i==end)can=1;
			bfs(i,end,p+1);
		}
	}
	return 0;
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	m=u.size();
	n=N;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)map[i][j]=-1;
	}
	for(int i=0;i<m;i++)
	{
		map[u[i]][v[i]]=i;
		map[v[i]][u[i]]=i;
	}
	for(int i=0;i<n;i++)
	{
		int c=-1;
		//cout<<i<<endl;
		for(int j=0;j<n;j++)
		{
			if(map[i][j]!=-1)
			{
				//cout<<j<<endl;
				if(c==-1)
				{
					c=j;
					tmpans[i][0]=1;
					tmpans[i][1]=map[i][j];
				}
				else
				{
					for(int k=0;k<n;k++)tag[k]=0;
					tag[c]=1;
					s1=map[i][c];
					s2=map[i][j];
					bfs(c,j,0);
					if(can==1)
					{
						std::vector<int> r(n - 1);
						for(int k=0;k<n-1;k++)r[k]=road[k];
						//cout<<c<<endl;
						r[n-2]=map[i][c];
						//for(int k=0;k<n-1;k++)cout<<r[k]<<" ";
						//cout<<endl;
						int a= count_common_roads(r);
						r[n-2]=map[i][j];
						//for(int k=0;k<n-1;k++)cout<<r[k]<<" ";
						//cout<<endl;
						int b= count_common_roads(r);
						//cout<<a<<" "<<b<<endl;
						if(a==b)
						{
							tmpans[i][0]++;
							tmpans[i][tmpans[i][0]]=map[i][j];
						}
						else if(a<b)
						{
							tmpans[i][0]=1;
							tmpans[i][1]=map[i][j];
							c=j;
						}
					}
					if(can==0)
					{
						tmpans[i][0]++;
						tmpans[i][tmpans[i][0]]=map[i][j];
					}
				}
			}
			//for(int k=1;k<=tmpans[i][0];k++)cout<<tmpans[i][k]<<" ";
			//cout<<endl;
		}
		//cout<<endl;
	}
	std::vector<int> r(n - 1);
	int p=0;
	for(int i=0;i<n;i++)
	{
		//cout<<i<<endl;
		for(int j=1;j<=tmpans[i][0];j++)
		{
			if(anstag[tmpans[i][j]]==0)
			{
				anstag[tmpans[i][j]]=1;
				r[p]=tmpans[i][j];	
				//cout<<r[p]<<" ";
				p++;
			}
		}
		//cout<<endl;
	}
	return r;
}

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