Submission #520441

#	Time	Username	Problem	Language	Result	Execution time	Memory
520441		ComPhyPark	Simurgh (IOI17_simurgh)	C++14	100 / 100	146 ms	6048 KiB

simurgh

#include "simurgh.h"
#include<utility>
#include<queue>
#include<algorithm>
#define x first
#define y second
#define pi pair<int,int>
using namespace std;
vector<vector<pi>>l;
vector<int>mm;
int vs[505], p[505], pl[505], up[505], cs[505], T = 1;
void dfs(int n, int p) {
	::p[n] = p;
	vs[n] = T++;
	for (pi e : l[n]) {
		if (e.x == p) {
			pl[n] = e.y;
		}
		if (vs[e.x] == 0)dfs(e.x, n);
	}
}
int f(int n) {
	if (n == up[n])return n;
	return up[n] = f(up[n]);
}
void un(int a, int b) {
	a = f(a);
	b = f(b);
	up[a] = b;
}
vector<int> find_roads(int n, vector<int>u, vector<int>v) {
	int i, j, r, m = v.size(), k, nn, ln;
	vector<int>qv;
	mm.resize(m, -1);
	l.resize(n);
	while (m--) {
		l[u[m]].push_back({ v[m],m });
		l[v[m]].push_back({ u[m],m });
	}
	m = u.size();
	dfs(0, -1);
	for (i = 1; i < n; i++)qv.push_back(pl[i]);
	k = count_common_roads(qv);
	//printf("##%d##\n", k);
	for (i = 1; i < n; i++) {
		//for (j = 0; j < m; j++)printf("%d ", mm[j]);
		//printf("\n");
		nn = ln = p[i];
		for (pi e : l[i]) {
			if (vs[e.x] < vs[nn]) {
				nn = e.x;
				ln = e.y;
			}
		}
		//printf("%d %d\n", i, p[i]);
		if (nn == p[i])continue;
		//printf("%d [%d,%d]\n", i, nn, ln);
		int b = 0, c = 1;
		for (j = i; j != nn; j = p[j]) {
			r = pl[j];
			if (mm[r] >= 0)continue;
			c = 0;
			qv.clear();
			qv.push_back(ln);
			for (int ii = 1; ii < n; ii++)if (pl[ii] != r)qv.push_back(pl[ii]);
			mm[r] = 3 + count_common_roads(qv) - k;//3+that road-this road
			if (mm[r] != 3)b = mm[r] - 3;
		}
		if (c)continue;
		if (b == 1) {
			//printf("Case 1\n");
			for (j = i; j != nn; j = p[j]) {
				r = pl[j];
				if (mm[r] > 1) {
					mm[r] = 4 - mm[r];
				}
			}
		}
		else if (b == -1) {
			//printf("Case 2\n");
			for (j = i; j != nn; j = p[j]) {
				r = pl[j];
				if (mm[r] > 1) {
					mm[r] = 3 - mm[r];
				}
			}
		}
		else {
			//printf("Case 3\n");
			int K = -1;
			for (j = i; j != nn; j = p[j]) {
				r = pl[j];
				if (mm[r] < 2) {
					qv.clear();
					qv.push_back(ln);
					for (int ii = 1; ii < n; ii++)if (pl[ii] != r)qv.push_back(pl[ii]);
					K = count_common_roads(qv) - k + mm[r];
					break;
				}
			}
			//printf("[%d]", K);
			if (K < 0) {
				//printf("ALL FIRST\n");
				for (j = i; j != nn; j = p[j]) {
					r = pl[j];
					mm[r] = 0;
				}
			}
			else {
				//printf("PAST EXISTS\n");
				for (j = i; j != nn; j = p[j]) {
					r = pl[j];
					if (mm[r] < 2)continue;
					mm[r] = K;
				}
			}
		}
	}
	//for (j = 0; j < m; j++)printf("%d ", mm[j]);
	//printf("\n");
	for (i = 1; i < n; i++) {
		if (mm[pl[i]] < 0)mm[pl[i]] = 1;
	}
	//for (j = 0; j < m; j++)printf("%d ", mm[j]);
	//printf("\n");
	queue<int>q;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)up[j] = j;
		qv.clear();
		for (pi e : l[i]) {
			qv.push_back(e.y);
			un(e.x, i);
		}
		k = 0;
		for (j = 1; j < n; j++) {
			if (f(j) != f(p[j])) {
				un(j, p[j]);
				qv.push_back(pl[j]);
				k += mm[pl[j]];
			}
		}
		cs[i] = count_common_roads(qv) - k;
		if (cs[i] == 1)q.push(i);
	}
	//for (i = 0; i < n; i++)printf("%d ", cs[i]);
	//printf("\n");
	//m = u.size();
	//for (i = 0; i < m; i++)printf("%d ", mm[i]);
	//printf("\n");
	vector<pi>vv;
	while (q.size()) {
		i = q.front();
		q.pop();
		//printf("Test: %d\n", i);
		if (cs[i] != 1)continue;
		//printf("Yeah\n");
		vv.clear();
		for (pi e : l[i]) {
			if (cs[e.x])vv.push_back(e);
		}
		while (vv.size() > 1) {
			//printf("[ ");
			//for (pi e : vv)printf("%d ", e.y);
			//printf("]\n");
			for (j = 0; j < n; j++)up[j] = j;
			qv.clear();
			for (j = 0; j < vv.size() / 2; j++) {
				qv.push_back(vv[j].y);
				un(vv[j].x, i);
			}
			k = 0;
			for (j = 1; j < n; j++) {
				if (f(j) != f(p[j])) {
					un(j, p[j]);
					qv.push_back(pl[j]);
					k += mm[pl[j]];
				}
			}
			//printf("%d %d\n", k, count_common_roads(qv));
			if (count_common_roads(qv) == k) {
				vv.erase(vv.begin(), vv.begin() + (vv.size() / 2));
			}
			else {
				vv.erase(vv.begin() + (vv.size() / 2), vv.end());
			}
		}
		//printf("[ ");
		//for (pi e : vv)printf("%d ", e.y);
		//printf("]\n");
		for (pi e : l[i]) {
			if (e.x == vv[0].x) {
				mm[e.y] = 1;
				cs[e.x]--;
				if (cs[e.x] == 1)q.push(e.x);
			}
			else if (mm[e.y] == -1) {
				mm[e.y] = 0;
			}
		}
		cs[i] = 0;
	}
	m = u.size();
	//for (i = 0; i < m; i++)printf("%d ", mm[i]);
	//printf("\n");
	vector<int>ans;
	for (i = 0; i < m; i++) {
		if (mm[i] == 1)ans.push_back(i);
	}
	return ans;
}

Compilation message (stderr)

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

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