Submission #114740

#	Time	Username	Problem	Language	Result	Execution time	Memory
114740		faustaadp	Simurgh (IOI17_simurgh)	C++17	30 / 100	109 ms	3440 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,tim;
ll X[125050];
ll Y[125050];
ll b[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(r[ii]);
		}
	ll mi=1e18,ya=0;
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
	//		cout<<aa<<" "<<ii<<"\n";
			if(r[aa]==ii)
				continue;
			b[ii]=1;
			tan.pb(ii);
			ll tom=count_common_roads(tan);
			isi.pb(mp(-tom,ii));
			mi=min(mi,tom);
			tan.pop_back();
			if(tom>tim)
			{
				ya=1;
				break;
			}
		}
//	cout<<aa<<" "<<ya<<"\n";
	if(!ya)
		return ;
	if(isi.empty())
		return ;
	sort(isi.begin(),isi.end());
	r[aa]=isi[0].se;
	tim=-isi[0].fi;
}
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);
		}
	//while(1);
	tim=count_common_roads(r);
	for(i=0;i<r.size();i++)
	{
		isi.clear();
		cek(i);
		//cout<<i<<" "<<r[i]<<"\n";
	}
	//for(i=0;i<r.size();i++)
	return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'void cek(ll)':
simurgh.cpp:27: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:78:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++)
          ~^~~~~~~~~

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