제출 #114715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114715		faustaadp	Simurgh (IOI17_simurgh)	C++17	0 / 100	2 ms	384 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,p[550],i;
ll X[125050];
ll Y[125050];
vector<int> r;
vector<pair<ll,ll> > isi;
ll car(ll aa)
{
	if(p[aa]==aa)
		return aa;
	else
		return p[aa]=car(p[aa]);
}
void cek(ll aa)
{
	vector<int> tan;
	ll ii;
	for(ii=0;ii<n;ii++)p[ii]=ii;
	for(ii=0;ii<r.size();ii++)
		if(ii!=aa)
		{
			p[car(X[r[ii]])]=car(Y[r[ii]]);
			tan.pb(ii);
		}
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
			tan.pb(ii);
			isi.pb(mp(-count_common_roads(tan),ii));
			tan.pop_back();
		}
	sort(isi.begin(),isi.end());
	r[aa]=isi[0].se;
}
std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) 
{
	n=N;
	m=U.size();
	for(i=0;i<m;i++)
		X[i]=U[i];
	for(i=0;i<m;i++)
		Y[i]=V[i];
	for(i=0;i<n;i++)p[i]=i;
	for(i=0;i<m;i++)
		if(car(U[i])!=car(V[i]))
		{
			p[car(U[i])]=car(V[i]);
			r.pb(i);
		}
	for(i=0;i<r.size();i++)
	{
	//	cout<<i<<" "<<r[i]<<"\n";
		isi.clear();
		cek(i);
	}
	if(count_common_roads(r)!=n-1)
		while(1);
	//for(i=0;i<r.size();i++)
	return r;
}

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

simurgh.cpp: In function 'void cek(ll)':
simurgh.cpp:26:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<r.size();ii++)
           ~~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++)
          ~^~~~~~~~~

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