Submission #838621

#	Time	Username	Problem	Language	Result	Execution time	Memory
838621		prvocislo	Simurgh (IOI17_simurgh)	C++17	30 / 100	3075 ms	6512 KiB

simurgh

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "simurgh.h"
typedef long long ll;
typedef long double ld;
using namespace std;

int n;
vector<int> u, v;

vector<int> p;
void clean() { p.assign(n, -1); for (int i = 0; i < n; i++) p[i] = i; }
int root(int i) { return p[i] == i ? i : p[i] = root(p[i]); }
bool merge(int k)
{
	int i = u[k], j = v[k];
	i = root(i), j = root(j);
	if (i == j) return false;
	p[i] = j;
	return true;
}

int count_common_roads(const vector<int>& r); 

vector<int> find_roads(int N, vector<int> U, vector<int> V)
{
	n = N, u = U, v = V;
	int m = u.size();
	set<int> g, r;
	for (int i = 0; i < m; i++) r.insert(i);
	while (!r.empty())
	{
		clean();
		vector<int> e;
		for (int i : g) merge(i), e.push_back(i);
		for (int i : r) if (merge(i)) e.push_back(i);
		for (int i : e) r.erase(i);
		if (r.empty())
		{
			sort(e.begin(), e.end());
			return e;
		}
		e.push_back(*r.begin());
		r.erase(r.begin());
		vector<pair<int, int> > c; // pre tie na cykle - { pocet zlatych ciest, ktory sme dali prec }
		for (int i : e) if (!g.count(i))
		{
			clean();
			vector<int> e2;
			for (int j : e) if (i != j)
			{
				if (!merge(j)) break;
				e2.push_back(j);
			}
			if (e2.size() < n - 1) r.insert(i);
			else c.push_back({ count_common_roads(e2), i });
		}
		int mx = max_element(c.begin(), c.end())->first;
		for (pair<int, int> p : c) if (p.first == mx - 1)
		{
			g.insert(p.second);
		}
	}
	return vector<int>(g.begin(), g.end());
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:67:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |    if (e2.size() < n - 1) r.insert(i);
      |        ~~~~~~~~~~^~~~~~~

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