제출 #283243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283243		MohamedAhmed04	Simurgh (IOI17_simurgh)	C++14	13 / 100	3062 ms	384 KiB

simurgh

#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 ;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30