oj.uz

Submission #283243

# Submission time Handle Problem Language Result Execution time Memory
283243 2020-08-25T12:09:39 Z MohamedAhmed04 Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 384 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
//#include "grader.cpp"

using namespace std ;

const int MAX = 504 ;

int par[MAX] ;
int N , M ;
vector<int>U,V ;

void init()
{
	for(int i = 0 ; i < N ; ++i)
		par[i] = i ;
}

int root(int node)
{
	if(par[node] == node)
		return node ;
	return (par[node] = root(par[node])) ;
}

void Union(int x , int y)
{
	int a = root(x) ;
	int b = root(y) ;
	par[a] = b ;
}

vector<int>vv ;
vector<int>ans ;

void solve(int i)
{
	if(M-i < N-1-vv.size())
		return ;
	if(vv.size() == N-1)
	{
		init() ;
		for(auto &j : vv)
		{
			if(root(U[j]) == root(V[j]))
				return ;
			Union(U[j] , V[j]) ;
		}
		int x = count_common_roads(vv) ;
		if(x == N-1)
			ans = vv ;
		return ;
	}
	vv.push_back(i) ;
	solve(i+1) ;
	vv.pop_back() ;
	solve(i+1) ;
}

std::vector<int> find_roads(int n, vector<int> u, vector<int> v) 
{
	N = n , M = u.size() , U = u , V = v ;
	solve(0) ;
	return ans ;
}

Compilation message

simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  if(M-i < N-1-vv.size())
      |     ~~~~^~~~~~~~~~~~~~~
simurgh.cpp:40:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |  if(vv.size() == N-1)
      |     ~~~~~~~~~~^~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Incorrect 30 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 Correct 9 ms 256 KB correct
2 Correct 9 ms 256 KB correct
3 Correct 9 ms 256 KB correct
4 Correct 1 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 2 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 1 ms 256 KB correct
12 Correct 1 ms 256 KB correct
13 Correct 9 ms 256 KB correct
14 Execution timed out 3062 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -