Submission #289496

#	Time	Username	Problem	Language	Result	Execution time	Memory
289496		eohomegrownapps	Simurgh (IOI17_simurgh)	C++14	51 / 100	204 ms	3204 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

//count_common_roads

vector<int> u;
vector<int> v;
vector<int> royal; // -1
int n;
int e;

//int count_common_roads(vector<int> &r)

struct UFDS{
	int n;
	vector<int> parent;
	UFDS(int _n){
		n = _n;
		parent.resize(n);
		for (int i = 0; i<n; i++){
			parent[i]=i;
		}
	}

	int root(int i){
		if (parent[i]==i){return i;}
		return parent[i]=root(parent[i]);
	}

	void connect(int a, int b){
		int ra = root(a);
		int rb = root(b);
		if (ra==rb){return;}
		parent[ra]=rb;
	}

	bool connected(int a, int b){
		return root(a) == root(b);
	}
};

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
	n=N; u=U; v=V; e=u.size();
	royal.resize(e,-1);
	vector<int> ans;
	while (ans.size()<n-1){
		/*cout<<"royal: ";
		for (int i : ans){
			cout<<i<<' ';
		}cout<<endl;*/
		UFDS ufds(n);
		// add all royal roads first
		vector<int> mst;
		for (int i = 0; i<e; i++){
			if (royal[i]==1){
				mst.push_back(i);
				ufds.connect(u[i],v[i]);
			}
		}
		for (int i = 0; i<e; i++){
			if (mst.size()==n-2){
				break;
			}
			if (royal[i]==-1 && !ufds.connected(u[i],v[i])){
				mst.push_back(i);
				ufds.connect(u[i],v[i]);
			}
		}
		/*for (int i : mst){
			cout<<i<<' ';
		}cout<<endl;*/
		// try all edges
		vector<int> edges;
		vector<int> values;
		int maxval = 0;
		for (int i = 0; i<e; i++){
			if (royal[i]!=-1){continue;}
			if (ufds.connected(u[i],v[i])){continue;}
			// try connecting edge
			mst.push_back(i);
			values.push_back(count_common_roads(mst));
			mst.pop_back();
			edges.push_back(i);
			maxval=max(maxval,values.back());
		}
		for (int i = 0; i<edges.size(); i++){
			if (values[i]==maxval){
				royal[edges[i]]=1;
				ans.push_back(edges[i]);
			} else {
				royal[edges[i]]=0;
			}
		}
	}
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  while (ans.size()<n-1){
      |         ~~~~~~~~~~^~~~
simurgh.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |    if (mst.size()==n-2){
      |        ~~~~~~~~~~^~~~~
simurgh.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int i = 0; i<edges.size(); i++){
      |                   ~^~~~~~~~~~~~~

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