Submission #963636

#	Time	Username	Problem	Language	Result	Execution time	Memory
963636		Itamar	Simurgh (IOI17_simurgh)	C++14	100 / 100	113 ms	7516 KiB

simurgh

using namespace std;
#include <vector>
#define vi vector<int>
#include "simurgh.h"
#define pi pair<int,int>
#include <random>
#define x first
#define y second
const int siz = 501;

int ans[siz][siz];
int in[siz][siz];
vi fr[siz];
int h[siz];
int pad[siz];
vi u, v;
int n;
bool vis[siz];
vi tr;
int m;
void dfs(int i) {
	if (vis[i])return;
	vis[i] = 1;
	for (int f : fr[i]) {
		if (!vis[f]) {
			h[f] = h[i] + 1;
			pad[f] = i;
			tr.push_back(in[i][f]);
			dfs(f);
		}
	}
}
static int find(int node, vi&parent) {
	return (parent[node] == node ? node : parent[node] = find(parent[node],parent));
}

static bool merge(int v1, int v2, vi& parent, vi& siz) {
	v1 = find(v1,parent);
	v2 = find(v2,parent);
	if (v1 == v2)
		return false;
	if (siz[v1] > siz[v2])swap(v1, v2);
	parent[v1] = v2;
	if (siz[v1] == siz[v2])siz[v2]++;
	return true;
}
int common(vi ed) {
	int mi = 0;
	vi q = ed;
	vi parent(n); for (int i = 0; i < n; i++)parent[i] = i;
	vi siz(n);
	for (int i : ed)merge(u[i], v[i],parent,siz);
	for (int i : tr) {
		if (merge(u[i], v[i], parent, siz)) {
			if(ans[u[i]][v[i]]==1)mi++;
			q.push_back(i);
		}
	}
	return count_common_roads(q) - mi;
}
void check(vi ed, int f) {
	if (ed.size() == 1) {
		ans[u[ed[0]]][v[ed[0]]] = 1;
		return;
	}
	int s = ed.size();
	vi vec1, vec2; 
	for (int i = 0; i < s; i++) {
		if (i < s / 2)vec1.push_back(ed[i]);
		else vec2.push_back(ed[i]);
	}
	int h = common(vec1);
	if (h>0) {
		check(vec1, h);
	}
	if (f-h>0)check(vec2, f-h);
}
vi find_roads(int N, vi U, vi V) {
	u = U, v = V;
	n = N;
	m = u.size();
	for (int i = 0; i < m; i++) {
		fr[u[i]].push_back(v[i]);
		fr[v[i]].push_back(u[i]);
		ans[u[i]][v[i]] = -1;
		ans[v[i]][u[i]] = -1;
		in[u[i]][v[i]] = i;
		in[v[i]][u[i]] = i;
	}
	dfs(0);
	int a = count_common_roads(tr);

	for (int i = 0; i < n; i++) {
		pi p={1e9,1e9};
		for (int j : fr[i]) {
			p = min(p, { h[j],j });
		}
		vi cyc = {in[i][p.y]};
		if (p.x >= h[i] - 1)continue;
		int t = i;
		while (t != p.y) {
			cyc.push_back({ in[t][pad[t]] });
			t = pad[t];
		}
		vi can = { a };
		vi ts(2,-1);
		for (int ed : cyc) {
			if (ed == cyc[0])continue;
			vi q = {cyc[0]};
			if (ans[u[ed]][v[ed]] != -1 && ts[ans[u[ed]][v[ed]]] != -1) {
				can.push_back(ts[ans[u[ed]][v[ed]]]); continue;
			}
			for (int j : tr) {
				if (j != ed) {
					q.push_back(j);
				}
			}
			int b = count_common_roads(q);
			can.push_back(b);
			if (ans[u[ed]][v[ed]] != -1)ts[ans[u[ed]][v[ed]]] = b;
		}
		int maxi = a; 
		for (int j : can)maxi = max(j, maxi);
		for (int j = 0; j < can.size(); j++) {
			if (can[j] < maxi) {
				ans[u[cyc[j]]][v[cyc[j]]] = 1;
			}
			else ans[u[cyc[j]]][v[cyc[j]]] = 0;
		}
	}
	for (int i : tr)if (ans[u[i]][v[i]] == -1)ans[u[i]][v[i]] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ans[i][j] != -1)ans[j][i] = ans[i][j];
		}
	}

	for (int d = 1; d < n; d++) {
		vi vec;
		for (int i = 0; i + d < n; i++) {
			if (ans[i][i + d] == -1)vec.push_back(in[i][i + d]);
		}
		int h = common(vec);
		if(h)check(vec,h);
	}

	vi res;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (ans[i][j] == 1 || ans[j][i] == 1)res.push_back(in[i][j]);
		}
	}
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for (int j = 0; j < can.size(); j++) {
      |                   ~~^~~~~~~~~~~~

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