Submission #54186

#	Time	Username	Problem	Language	Result	Execution time	Memory
54186		radoslav11	Simurgh (IOI17_simurgh)	C++14	100 / 100	205 ms	12548 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 9);
const int MAXM = (1 << 18);

struct dsu
{
	int par[MAXN], sz[MAXN];

	void init(int n) 
	{  
		for(int i = 0; i <= n; i++) 
			par[i] = i, sz[i] = 1;
	}

	int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }

	bool connected(int x, int y) { return root(x) == root(y); }

	void unite(int u, int v)
	{
		u = root(u);
		v = root(v);

		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);

		par[v] = u;
		sz[u] += sz[v];
	}
} d;

int m, n;
pair<int, int> ed[MAXM];
vector<pair<int, int> > adj[MAXN];
int dfs_time, low[MAXN], disc[MAXN];
int low_edge[MAXN], ver[MAXN];
int E[MAXM];

int par[MAXN], pe[MAXN];
vector<int> li[MAXM];
vector<int> le, Tr;

bool cmp(int i, int j) { return min(low[ed[i].first], low[ed[i].second]) < min(low[ed[j].first], low[ed[j].second]); }

void tarjan(int u, int pr)
{
	low[u] = disc[u] = ++dfs_time;
	ver[dfs_time] = u;
	low_edge[u] = -1;

	for(auto e: adj[u])
		if(e.first != pr)
		{
			int v = e.first;
			if(!disc[v])
			{
				par[v] = u;
				pe[v] = e.second;
				tarjan(v, u);

				if(chkmin(low[u], low[v])) 
					low_edge[u] = low_edge[v];

				if(disc[u] < low[v])
					E[e.second] = 1;
			}
			else if(chkmin(low[u], disc[v]))
				low_edge[u] = e.second;
		}

	if(low_edge[u] != -1)
		le.push_back(low_edge[u]);

	if(u != pr) Tr.push_back(pe[u]);
}

int R[MAXM];
int initial;

int diff(int rem, int add)
{
	vector<int> tmp;
	for(int e: Tr)
		if(e == rem) tmp.push_back(add);
		else tmp.push_back(e);

	return count_common_roads(tmp) - initial;
}

int cnt_good(vector<int> L)
{
	d.init(::n);
	vector<int> tmp = L;
	for(int i: L)
		d.unite(ed[i].first, ed[i].second);

	int to_rem = 0;
	for(int i: Tr)
		if(!d.connected(ed[i].first, ed[i].second))
			to_rem += E[i], d.unite(ed[i].first, ed[i].second), tmp.push_back(i);

	return count_common_roads(tmp) - to_rem;
}

void rec(vector<int> &l, int sum)
{
	if(sum == 0) 
		return;

	if(l.size() == 1)
	{
		E[l.back()] = 1;
		return;
	}

	vector<int> m1, m2;
	for(int i = 0; i < (int)l.size() / 2; i++) m1.push_back(l[i]);
	for(int i = l.size() / 2; i < (int)l.size(); i++) m2.push_back(l[i]);

	int c1 = cnt_good(m1), c2 = sum - c1;
	rec(m1, c1);
	rec(m2, c2);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) 
{
	::n = n;
	::m = u.size();
	for(int i = 0; i < ::m; i++)
	{
		ed[i] = {u[i], v[i]};
		adj[u[i]].push_back({v[i], i});
		adj[v[i]].push_back({u[i], i});
		E[i] = -1;
	}	

	tarjan(0, 0);

	sort(le.begin(), le.end());
	le.erase(unique(le.begin(), le.end()), le.end());
	sort(le.begin(), le.end(), cmp);

	initial = count_common_roads(Tr);

	for(int i: le)
	{
		int from = ed[i].first, to = ed[i].second;
		if(disc[from] > disc[to]) swap(from, to);

		while(to != from)
		{
			li[i].push_back(pe[to]);
			to = par[to];
		}

		int has = -1;
		for(int e: li[i])
			if(E[e] != -1)
				has = e;

		if(has != -1)
		{
			int df = diff(has, i);
			if(df == 0) E[i] = E[has];
			else E[i] = E[has] ^ 1;

			for(int e: li[i])
				if(E[e] == -1)
				{
					int df = diff(e, i);
					if(df == 0) E[e] = E[i];
					else E[e] = E[i] ^ 1;
				}
		}
		else
		{
			bool fl = 0;
			for(int e: li[i])
			{
				R[e] = diff(e, i);
				if(R[e]) fl = 1;
			}	

			if(!fl)
			{
				E[i] = 0;
				for(int e: li[i])
					E[e] = 0;
			}
			else
			{
				for(int e: li[i])
					if(R[e])
					{
						if(R[e] == 1) E[i] = 1;
						else E[i] = 0;
						break;
					}
				
				for(int e: li[i])
					if(E[e] == -1)
					{
						int df = R[e];
						if(df == 0) E[e] = E[i];
						else E[e] = E[i] ^ 1;
					}
			}
		}
	}

	for(int i = 0; i < n; i++)
	{
		int cnt = 0;
		vector<int> candidates;

		for(auto e: adj[i])
			if(E[e.second] == -1)
				candidates.push_back(e.second);
	
		cnt = cnt_good(candidates);
		rec(candidates, cnt);
	}

	vector<int> result;
	for(int i = 0; i < ::m; i++)
		if(E[i] == 1) 
			result.push_back(i);

	return result;
}

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