Submission #1089844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089844		vjudge1	Simurgh (IOI17_simurgh)	C++17	13 / 100	47 ms	932 KiB

simurgh

#include "simurgh.h"
#include <array>
using namespace std;

int n;
vector <array <int, 3>> edges;
vector <int> answer;

struct dsu {
	vector <int> parent;
	dsu(int n) {
		parent.resize(n);
		for (int i = 0; i < n; i++) parent[i] = i;
	}
	int root(int x) {
		return parent[x] == x ? x : parent[x] = root(parent[x]);
	}
	void unite(int x, int y) {
		parent[root(x)] = root(y);
	}
};

void getVector(int index, vector <int> &added, dsu d) {
	if (!answer.empty()) return;
	if (added.size() == n - 1) {
		if (count_common_roads(added) == n - 1) {
			answer = added;
			return;
		}
		return;
	}
	if (index == edges.size()) return;
	if (d.root(edges[index][0]) != d.root(edges[index][1])) {
		dsu d2 = d;
		d2.unite(edges[index][0], edges[index][1]);
		added.push_back(edges[index][2]);
		getVector(index + 1, added, d2);
		added.pop_back();
	}
	getVector(index + 1, added, d);
}

vector <int> find_roads(int N, vector <int> u, vector <int> v) {
	n = N;
	for (int i = 0; i < u.size(); i++) {
		edges.push_back({u[i], v[i], i});
	}
	vector <int> a;
	getVector(0, a, dsu(n));
	return answer;
}

Compilation message (stderr)

simurgh.cpp: In function 'void getVector(int, std::vector<int>&, dsu)':
simurgh.cpp:25:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |  if (added.size() == n - 1) {
      |      ~~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:32:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  if (index == edges.size()) return;
      |      ~~~~~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

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