oj.uz

Submission #117894

# Submission time Handle Problem Language Result Execution time Memory
117894 2019-06-17T10:01:45 Z tinjyu Simurgh (IOI17_simurgh) C++14
0 / 100
 2 ms 384 KB 
#include "simurgh.h"
#include <iostream>
using namespace std;
long long int Na,can,tag[505],map[505][505],r,road[505],tmpans[505][505],s1,s2,anstag[250000],p;
int bfs(int x)
{
	for(int i=0;i<Na;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];
			p++;
			bfs(i);
		}
	}
	return 0;
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	Na=N;
	long long int M=u.size();
	for(int i=0;i<Na;i++)
	{
		for(int j=0;j<Na;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<Na;i++)
	{
		int c=-1;
		//cout<<i<<endl;
		for(int j=0;j<Na;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<Na;k++)tag[k]=0;
					tag[c]=1;
					s1=map[i][c];
					s2=map[i][j];
					p=0;
					bfs(c);
					bfs(i);
					int tmp=0;
					for(int k=0;k<Na;k++)tmp+=tag[k];
					if(tmp==Na)
					{
						std::vector<int> r(Na - 1);
						for(int k=0;k<Na-1;k++)r[k]=road[k];
						for(int k=0;k<Na;k++)tag[k]=0;
						for(int k=0;k<Na-1;k++)
						{
							int t=r[k];
							//cout<<t<<" "<<u[t]<<" "<<v[t]<<"  ";
							tag[u[t]]++;
							tag[v[t]]++;
						}
						//cout<<endl;
						for(int k=0;k<Na;k++)
						{
							//cout<<tag[k]<<" ";
						}
						//cout<<endl;
						//cout<<c<<endl;
						r[Na-2]=map[i][c];
						//for(int k=0;k<n-1;k++)cout<<r[k]<<" ";
						//cout<<endl;
						int a= count_common_roads(r);
						r[Na-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;
						}
					}
					else
					{
						tmpans[i][0]++;
						tmpans[i][tmpans[i][0]]=map[i][j];
					}
				}
			}
			//cout<<endl;
			//for(int k=1;k<=tmpans[i][0];k++)cout<<tmpans[i][k]<<" ";
			//cout<<endl;
		}
		//cout<<endl;
	}
	std::vector<int> r(Na - 1);
	//cout<<"can"<<endl;

	int p=0;
	for(int i=0;i<Na;i++)
	{
		//cout<<i<<endl;
		//cout<<tmpans[i][0]<<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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Incorrect 2 ms 256 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB WA in grader: NO
2 Halted 0 ms 0 KB -