Submission #153483

#	Time	Username	Problem	Language	Result	Execution time	Memory
153483		mieszko11b	Simurgh (IOI17_simurgh)	C++14	100 / 100	274 ms	8396 KiB

simurgh

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

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int n, m;
vector<int> G[507];
int deg[507];
vector<int> ok[507];
int p[507], h[507];
int correct[507];
bool tree_edge[507][507];
int edge_nr[507][507];
vector<int> T;
int edge_corr[507 * 507 / 2];
bool vis[507];
ii edgev[507 * 507 / 2];

void dfs(int w) {
	for(int u : G[w]) {
		if(!vis[u]) {
			vis[u] = 1;
			p[u] = w;
			h[u] = h[w] + 1;
			tree_edge[w][u] = tree_edge[u][w] = 1;
			T.push_back(edge_nr[w][u]);
			dfs(u);
		}
	}
}

void check_path(int a, int b) {
	int c = b;
	while(c != a && correct[c] == -1)
		c = p[c];
	if(c == b)
		return ;
		
	vector<int> base, cycle;
	bool in_cycle[507 * 507 / 2];
	memset(in_cycle, 0, sizeof in_cycle);
	int w = b;
	while(h[w] > h[a]) {
		in_cycle[edge_nr[w][p[w]]] = true;
		cycle.push_back(edge_nr[w][p[w]]);
		w = p[w];
	}
	cycle.push_back(edge_nr[a][b]);
	
	for(int x : T)
		if(!in_cycle[x])
			base.push_back(x);
	
	if(c == a) {
		vector<int> res;
		int minv = 1e9, maxv = -1;
		for(int x : cycle) {
			vector<int> tmp = base;
			for(int y : cycle)
				if(x != y)
					tmp.push_back(y);
			res.push_back(count_common_roads(tmp));
			minv = min(minv, res.back());
			maxv = max(maxv, res.back());
		}
		
		if(minv == maxv) {
			int w = b;
			while(h[w] > h[a]) {
				correct[w] = 0;
				w = p[w];
			}
		} else {
			for(int i = 0 ; i < cycle.size() ; i++)
				if(res[i] == minv)
					edge_corr[cycle[i]] = 1;
				else
					edge_corr[cycle[i]] = 0;
					
			int w = b;
			while(h[w] > h[a]) {
				correct[w] = edge_corr[edge_nr[w][p[w]]];
				w = p[w];
			}
		}
		
		return ;
	}
	
	int known = correct[c];
	int knownv;
	vector<int> tmp = base;
	for(int x : cycle)
		if(x != edge_nr[c][p[c]])
			tmp.push_back(x);
	knownv = count_common_roads(tmp);
	
	w = b;
	while(w != c) {
		tmp = base;
		for(int x : cycle)
			if(x != edge_nr[w][p[w]])
				tmp.push_back(x);
		int res = count_common_roads(tmp);
		if(res == knownv)
			correct[w] = known;
		else
			correct[w] = (known + 1) % 2;
		w = p[w];
	}
}

struct FindUnion {
	int p[507];
	
	FindUnion() {
		for(int i = 0 ; i < n ; i++)
			p[i] = i;
	}
	
	int Find(int x) {
		if(p[x] == x)
			return x;
		return p[x] = Find(p[x]);
	}
	
	void Union(int x, int y) {
		int a = Find(x);
		int b = Find(y);
		
		if(a == b)
			return ;
			
		p[a] = b;
	}
};

int count_common(vector<int> F) {
	int sub = 0;
	FindUnion FU;
	for(int e : F) {
		FU.Union(edgev[e].X, edgev[e].Y);
	}
		
	for(int e : T) {
		if(FU.Find(edgev[e].X) !=  FU.Find(edgev[e].Y)) {
			sub += edge_corr[e];
			FU.Union(edgev[e].X, edgev[e].Y);
			F.push_back(e);
		}
	}
	
	int res = count_common_roads(F);
	return res - sub;
}

int find_one(int w, int a, int b) {
	if(a == b)
		return a;
		
	int mid = (a + b) / 2;
	vector<int> F;
	for(int i = a ; i <= mid ; i++) {
		int u = G[w][i];
		if(!ok[w][i])
			F.push_back(edge_nr[w][u]);
	}
	
	if(count_common(F))
		return find_one(w, a, mid);
	return find_one(w, mid + 1, b);
}

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++) {
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
		edge_nr[u[i]][v[i]] = edge_nr[v[i]][u[i]] = i;
		edgev[i] = {u[i], v[i]};
	}
	
	vis[0] = 1;
	dfs(0);
	
	memset(correct, -1, sizeof correct);

	vector<int> E;
	for(int i = 0 ; i < m ; i++)
		if(!tree_edge[u[i]][v[i]])
			E.push_back(i);
			
	sort(E.begin(), E.end(), [&u, &v](int a, int b) {
		int lcpha = min(h[u[a]], h[v[a]]);
		int lcphb = min(h[u[b]], h[v[b]]);
		if(lcpha != lcphb)
			return lcpha < lcphb;
		return a < b;
	});
	
	for(int e : E) {
		int a = u[e];
		int b = v[e];
		if(h[a] > h[b])
			swap(a, b);
		check_path(a, b);
	}

	for(int i = 1 ; i < n ; i++) {
		if(correct[i] == -1)
			correct[i] = 1;
		edge_corr[edge_nr[i][p[i]]] = correct[i];
	}
		
	for(int i = 0 ; i < n ; i++) {
		vector<int> tmp;
		for(int x : G[i])
			tmp.push_back(edge_nr[i][x]);
		deg[i] = count_common(tmp);
		ok[i].resize(G[i].size(), 0);
	}
	
	vector<int> res;
	
	while(res.size() + 1 < n) {
		for(int i = 0 ; i < n ; i++) {
			if(deg[i] == 1) {
				int x = find_one(i, 0, G[i].size());
				ok[i][x] = 1;
				int u = G[i][x];
				for(int j = 0 ; j < G[u].size() ; j++) {
					if(G[u][j] == i) {
						ok[u][j] = 1;
						break;
					}
				}
				res.push_back(edge_nr[i][u]);
				deg[u]--;
				deg[i]--;
				break;
			}
		}
	}
			
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'void check_path(int, int)':
simurgh.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < cycle.size() ; i++)
                    ~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:231:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(res.size() + 1 < n) {
        ~~~~~~~~~~~~~~~^~~
simurgh.cpp:237:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0 ; j < G[u].size() ; j++) {
                     ~~^~~~~~~~~~~~~

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