Submission #1018977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018977		lovrot	Simurgh (IOI17_simurgh)	C++17	100 / 100	660 ms	8428 KiB

simurgh

#include "simurgh.h"
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair<int, int> pii;

const int N = 510;
const int M = N * N;

int n, m, uu[M], vv[M];
vector<pii> g[N];

bool isb[M];
vector<pii> mst;

int dep[N], mind[N]; // memset(dep)

int dfstree(int u, int p, int pi) { 
	mind[u] = dep[u];
	for(pii e : g[u]) { 
		int v = e.X, i = e.Y;

		if(v != p) { 
			if(dep[v] == -1) { 
				dep[v] = dep[u] + 1;
				mind[u] = min(mind[u], dfstree(v, u, i));
			} else if( dep[v] < dep[u]) { 
				mind[u] = min(mind[u], dep[v]);
			}
		}
	}
	
	if(pi != -1 && mind[u] >= dep[u]) { 
		mst.PB({pi, 1});
		isb[pi] = 1;
	}

	return mind[u];
}

void bridge() { 
	memset(dep, -1, sizeof(dep));
	dep[0] = 0;
	dfstree(0, -1, -1);
}

int un[N], siz[N];

void clear() { 
	memset(un, -1, sizeof(un));
	for(int i = 0; i < n; ++i) { 
		siz[i] = 1;
	}
}

int trazi(int u) { return un[u] == -1 ? u : un[u] = trazi(un[u]); }
bool unija(int u, int v) { 
	u = trazi(u);
	v = trazi(v);
	if(u == v) { return 0; }

	if(siz[u] < siz[v]) { swap(u, v); }
	un[v] = u;
	siz[u] += siz[v];
	return 1;
}

vector<int> qry;

int fillup(vector<int> &e, bool f) { 
	clear();
	qry.clear();
	int ret = 0;

	for(int i : e) { 
		unija(uu[i], vv[i]);
		qry.PB(i);
	}

	if(f == 0) { 
		for(int i = 0; i < m; ++i) { 
			if(unija(uu[i], vv[i])) { 
				qry.PB(i);
			}
		}
	} else { 
		for(pii i : mst) { 
			if(unija(uu[i.X], vv[i.X])) { 
				qry.PB(i.X);
				ret += i.Y;
			}
		}
	}
	return ret;
}

int bio[N], bioe[M], val[M];
vector<int> tmp, cp, pth;

void comp(int u) { 
	if(bio[u] != -1) { return; }
	bio[u] = 0;
	cp.PB(u);

	for(pii e : g[u]) { 
		if(!isb[e.Y]) { 
			comp(e.X);
		}
	}
}

bool tried[N];
int spec[2], sp;

bool dfs(int u) {
	bio[u] = 1;
	tried[u] = 1;
	for(pii e : g[u]) { 
		int v = e.X, i = e.Y;
		if(!isb[i] && !bioe[i] && bio[v] != 1 && !tried[v]) { 
			tmp.PB(i);
			bioe[i] = 1;
			if(bio[v] == 2) { 
				spec[sp] = v;
				return 1;
			} else {
				if(dfs(v)) { 
					return 1; 
				}
				bioe[i] = 0;
				tmp.pop_back();
			}
		}
	}
	bio[u] = 0;
	return 0;
}

bool path(int u, int t, int pr = -1) { 
	if(u == t) { return 1; }
	bool ret = 0;
	for(pii p : g[u]) { 
		int v = p.X, ind = p.Y;
		if(v != pr && !isb[ind] && bioe[ind] == 1 && bio[v] == 2) { 
			if(path(v, t, u)) { 
				pth.PB(ind);
				return 1;
			}
		}
	}
	return 0;
}

void cycle(vector<int> &e) {
	pth.clear();
	path(spec[0], spec[1]);
	int f = -1;
	for(int i = 0; i < pth.size(); ++i) {
		if(val[pth[i]] == 0) { 
			f = i;
		}
	}

	int xam = -1;
	if(f != -1) { 
		vector<int> fu;
		for(int i = 0; i < pth.size(); ++i) { 
			if(i != f) {
				fu.PB(pth[i]);
			}
		}
		for(int i : e) { 
			fu.PB(i);
		}
		fillup(fu, 0);

		xam = count_common_roads(qry);
	}

	vector<pii> res;
	for(int i = 0; i < e.size(); ++i) { 
		vector<int> fu;
		for(int j : pth) {
			fu.PB(j);
		}
		for(int j = 0; j < e.size(); ++j) { 
			if(j != i) {
				fu.PB(e[j]);
			}
		}
		
		fillup(fu, 0);
		res.PB({e[i], count_common_roads(qry)});
		xam = max(xam, res.back().Y);
	}

	for(int i = 0; i < (int) res.size() - 1; ++i) { 
		mst.PB({res[i].X, xam - res[i].Y});
		val[res[i].X] = xam - res[i].Y;
	}
	bioe[res.back().X] = 0;
}

void ear() {
	memset(bio, -1, sizeof(bio));

	for(int i = 0; i < n; ++i) { 
		if(bio[i] == -1) { 
			cp.clear();
			comp(i);
			bio[i] = 2;

			for(int j : cp) { 
				if(bio[j] != 2) {
					tmp.clear();
					memset(tried, 0, sizeof(tried));
					sp = 0; dfs(j); 
					memset(tried, 0, sizeof(tried));
					sp = 1; dfs(j);
					
					cycle(tmp);

					for(int k : tmp) { 
						bio[uu[k]] = 2;
						bio[vv[k]] = 2;
					}
				}
			}
		}
	}
}

bool ans[M];
int deg[N], cnt = 0;

int query(vector<int> &q) {
	int d = fillup(q, 1);
	return count_common_roads(qry) - d;
}

int leaf(int u) { 
	vector<int> ng;	
	for(pii e : g[u]) { 
		if(!ans[e.Y]) { 
			ng.PB(e.Y); 
		}
	}

	for(; ng.size() > 1; ) {
		vector<int> q;
		
		int k = (ng.size() + 1) / 2;
		for(int i = 0; i < k; ++i) { 
			q.PB(ng[i]);
		}

		if(query(q)) { 
			ng.erase(ng.begin() + k, ng.end());
		} else {
			ng.erase(ng.begin(), ng.begin() + k);
		}
	}

	return ng[0];
}

vector<int> find_roads(int nn, vector<int> A, vector<int> B) {
	n = nn;
	m = A.size();
	for(int i = 0; i < m; ++i) { 
		uu[i] = A[i];
		vv[i] = B[i];
		g[uu[i]].PB({vv[i], i});	
		g[vv[i]].PB({uu[i], i});	
	}

	bridge();
	ear();

	for(int i = 0; i < n; ++i) { 
		vector<int> q;
		for(pii i : g[i]) { 
			q.PB(i.Y);
		}
	
		deg[i] = query(q);
	}

	for(; cnt < n - 1; ) { 
		for(int i = 0; i < n; ++i) { 
			if(deg[i] == 1) { 
				++cnt;
				int ind = leaf(i);
				ans[ind] = 1;
				--deg[uu[ind]];
				--deg[vv[ind]];
			}
		}
	}
	
	vector<int> ret;
	for(int i = 0; i < m; ++i) { 
		if(ans[i]) { 
			ret.PB(i);
		}
	}
	return ret;
}

Compilation message (stderr)

simurgh.cpp: In function 'bool path(int, int, int)':
simurgh.cpp:151:7: warning: unused variable 'ret' [-Wunused-variable]
  151 |  bool ret = 0;
      |       ^~~
simurgh.cpp: In function 'void cycle(std::vector<int>&)':
simurgh.cpp:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |  for(int i = 0; i < pth.size(); ++i) {
      |                 ~~^~~~~~~~~~~~
simurgh.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |   for(int i = 0; i < pth.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
simurgh.cpp:191:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |  for(int i = 0; i < e.size(); ++i) {
      |                 ~~^~~~~~~~~~
simurgh.cpp:196:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |   for(int j = 0; j < e.size(); ++j) {
      |                  ~~^~~~~~~~~~

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