Submission #114725

#	Time	Username	Problem	Language	Result	Execution time	Memory
114725		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];
ll z[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)
		{
			if(car(X[r[ii]])!=car(Y[r[ii]]))
				p[car(X[r[ii]])]=car(Y[r[ii]]);
			tan.pb(r[ii]);
		}
	for(ii=0;ii<m;ii++)
		if(car(X[ii])!=car(Y[ii]))
		{
		//	cout<<aa<<" "<<ii<<"\n";
			tan.pb(ii);
			isi.pb(mp(-count_common_roads(tan),ii));
			tan.pop_back();
		}
	sort(isi.begin(),isi.end());
	z[isi[0].se]=1;
//	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);
		}
	//cout<<count_common_roads(r)<<"\n";
	for(i=0;i<r.size();i++)
	{
		isi.clear();
		cek(i);
	//	cout<<i<<" "<<r[i]<<"\n";
	}
	r.clear();
	for(i=0;i<m;i++)
		if(z[i])
			r.pb(i);
	if(count_common_roads(r)!=n-1)
	{
		n=n/0;
		while(1);
	}
	//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:62:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++)
          ~^~~~~~~~~
simurgh.cpp:74:6: warning: division by zero [-Wdiv-by-zero]
   n=n/0;
     ~^~

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