Submission #73287

#	Time	Username	Problem	Language	Result	Execution time	Memory
73287		Sa1378	Simurgh (IOI17_simurgh)	C++17	51 / 100	218 ms	7092 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)510)
#define M ((int)151*1000)

int n,m;
pair <int,int> ed[M];
vector <int> e[N],edges,ed_id;
bool ans[M],mark[N];

void dfs(int x,int v)
{
	mark[x]=1;
	for(auto u:e[v])
		if(ed[u].first+ed[u].second-v==x)
		{
			ed_id.push_back(u);
			break;
		}
	for(auto u:e[x])
	{
		int p=ed[u].first+ed[u].second-x;
		if(!mark[p])
		{
			edges.push_back(u);
			dfs(p,v);
		}
	}
}

vector<int> find_roads(int n2,vector<int> u,vector<int> v)
{
	n=n2;m=u.size();
	for(int i=0;i<m;i++)
		ed[i]={v[i],u[i]},
		e[v[i]].push_back(i),
		e[u[i]].push_back(i);
	for(int i=0;i<n-1;i++)
	{
		memset(mark,0,sizeof mark);
		mark[i]=1;
		edges.clear();
		vector <vector <int> > groups;
		for(int j=0;j<n;j++)
			if(!mark[j])
			{
				ed_id.clear();
				dfs(j,i);
				groups.push_back(ed_id);
			}
		for(auto vec:groups)
		{
			vector <int> ex_ed;ex_ed=edges;
			for(auto vec2:groups)
				if(vec!=vec2)
					edges.push_back(vec2[0]);
			vector <int> res;
			for(auto u:vec)
			{
				if(ed[u].first+ed[u].second-i<i)
				{
					res.push_back(N);
					continue;
				}
				edges.push_back(u);
				res.push_back(count_common_roads(edges));
				edges.pop_back();
			}
			int mini=N;
			for(auto u:res)mini=min(mini,u);
			if(mini==N)
			{
				edges=ex_ed;
				continue;
			}
			bool flg=0;
			for(auto u:res)
				if(u==mini+1)
					flg=1;
			if(flg)
			{
				for(int j=0;j<vec.size();j++)
					if(res[j]==mini+1)
						ans[vec[j]]=1;
				edges=ex_ed;
				continue;
			}
			flg=0;
			for(int j=0;j<vec.size();j++)
				if(res[j]==N && ans[vec[j]])
					flg=1;
			if(!flg)
			{
				for(int j=0;j<vec.size();j++)
					if(res[j]!=N)
						ans[vec[j]]=1;
				edges=ex_ed;
				continue;
			}
			for(int j=0;j<vec.size();j++)
				if(res[j]==N && ans[vec[j]])
				{
					edges.push_back(vec[j]);
					int ex=count_common_roads(edges);
					edges.pop_back();
					if(ex==mini)
					{
						for(int k=0;k<vec.size();k++)
							if(res[k]==mini)
								ans[vec[k]]=1;
					}
					break;
				}
			edges=ex_ed;
		}
	}
	vector <int> res;
	for(int i=0;i<m;i++)
		if(ans[i])
			res.push_back(i);
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<vec.size();j++)
                 ~^~~~~~~~~~~
simurgh.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<vec.size();j++)
                ~^~~~~~~~~~~
simurgh.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<vec.size();j++)
                 ~^~~~~~~~~~~
simurgh.cpp:101:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<vec.size();j++)
                ~^~~~~~~~~~~
simurgh.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int k=0;k<vec.size();k++)
                   ~^~~~~~~~~~~

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