Submission #140030

#	Time	Username	Problem	Language	Result	Execution time	Memory
140030		arthurconmy	Simurgh (IOI17_simurgh)	C++14	13 / 100	3041 ms	376 KiB

simurgh

#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "simurgh.h"
#endif

using namespace std;

#ifdef ARTHUR_LOCAL
	// ifstream cin("input.txt");

	int global_cnt=0;

	int count_common_roads(vector<int> L)
	{
		for(auto l:L) cout << l << " ";
		cout << endl;

		global_cnt++;

		if(global_cnt<=3) return 1;
		return 3;
	}
#endif

vector<pair<int,int>> adj[50];
bool vis[50];
bool yes[50*50];
int reach=0;

void dfs(int v)
{
	vis[v]=1;
	reach++;

	for(auto u:adj[v])
	{
		if(vis[u.first] || !yes[u.second]) continue;

		dfs(u.first);
	}
}

// NB: count_common_roads() takes in a (n-1) sized vector and returns the number of royal roads in this spanning tree

vector<int> find_roads(int n, vector<int> U, vector<int> V) 
{
	int m = U.size();

	for(int i=0; i<m; i++)
	{
		adj[U[i]].push_back(make_pair(V[i],i));
		adj[V[i]].push_back(make_pair(U[i],i));
	}

	vector<int> perm;

	for(int i=1; i<n; i++) perm.push_back(1);
	while(perm.size() < U.size()) perm.push_back(0);

	sort(perm.begin(),perm.end());

	do
	{
		for(int i=0; i<m; i++) yes[i]=perm[i];
		for(int i=0; i<n; i++) vis[i]=0;
		reach=0;
		dfs(0);

		if(reach==n)
		{
			vector<int> cur;
			
			for(int i=0; i<m; i++)
			{
				if(yes[i]) cur.push_back(i);
			}

			if(count_common_roads(cur)==n-1) return cur;
		}

	} while(next_permutation(perm.begin(),perm.end()));
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		cout << find_roads(4,{0,0,0,1,1,2},{1,2,3,2,3,3})[0] << endl;
	}
#endif

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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