Submission #136941

#	Time	Username	Problem	Language	Result	Execution time	Memory
136941		rondojim	Simurgh (IOI17_simurgh)	C++17	51 / 100	275 ms	4164 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=tim,ya=0,ma=-1;
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
			if(b[ii]==1)
			{
				r[aa]=ii;
				return ;
			}
		}
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
	//		cout<<aa<<" "<<ii<<"\n";
			//b[ii]=1;
			if(b[ii]==2)
				continue;
			tan.pb(ii);
			ll tom=count_common_roads(tan);
			mi=min(mi,tom);
			tan.pop_back();
			isi.pb(mp(-tom,ii));
			/*
			if(tom>mi)
			{
	//			ya=1;
				break;
			}*/
		}
//	cout<<aa<<" "<<ya<<"\n";
	//if(!ya)
	//	return ;
	if(isi.empty())
		return ;
	sort(isi.begin(),isi.end());
	for(ii=0;ii<isi.size();ii++)
		if(isi[0].fi==isi[ii].fi)
			b[isi[ii].se]=1;
		else
			b[isi[ii].se]=2;
	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:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<isi.size();ii++)
           ~~^~~~~~~~~~~
simurgh.cpp:33:12: warning: unused variable 'ya' [-Wunused-variable]
  ll mi=tim,ya=0,ma=-1;
            ^~
simurgh.cpp:33:17: warning: unused variable 'ma' [-Wunused-variable]
  ll mi=tim,ya=0,ma=-1;
                 ^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:93: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: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30