oj.uz

Submission #140030

# Submission time Handle Problem Language Result Execution time Memory
140030 2019-08-01T22:22:46 Z arthurconmy Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 376 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB correct
2 Correct 16 ms 256 KB correct
3 Correct 8 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 3 ms 376 KB correct
13 Correct 7 ms 376 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB correct
2 Correct 16 ms 256 KB correct
3 Correct 8 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 3 ms 376 KB correct
13 Correct 7 ms 376 KB correct
14 Execution timed out 3041 ms 376 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB correct
2 Correct 16 ms 256 KB correct
3 Correct 8 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 3 ms 376 KB correct
13 Correct 7 ms 376 KB correct
14 Execution timed out 3041 ms 376 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB correct
2 Correct 16 ms 256 KB correct
3 Correct 8 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 4 ms 256 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 3 ms 376 KB correct
13 Correct 7 ms 376 KB correct
14 Execution timed out 3041 ms 376 KB Time limit exceeded
15 Halted 0 ms 0 KB -