Submission #706082

#	Time	Username	Problem	Language	Result	Execution time	Memory
706082		Soumya1	Simurgh (IOI17_simurgh)	C++17	0 / 100	1035 ms	4304 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 505;
int n, m;
int ad[mxN][mxN];
vector<int> g[mxN];
vector<pair<int, int>> edges;
struct DSU {
	int n;
	vector<int> par;
	DSU(int _n) {
		n = _n;
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int u) {
		return (u == par[u] ? u : find(par[u]));
	}
	bool unite(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return false;
		par[u] = v;
		return true;
	}
};
int query(vector<int> r) {
	return count_common_roads(r);
}
set<int> tree;
vector<int> nodes[mxN];
set<int> on;
int Myquery(vector<int> v) {
	vector<int> r;
	DSU dsu(n);
	for (int i : v) {
		auto [u, v] = edges[i];
		r.push_back(i);
		dsu.unite(u, v);
	}
	for (int i : on) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);	
	}
	for (int i : tree) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);
	}
	return query(r);
}
int init;
int reduction(vector<int> v) {
	vector<int> r;
	DSU dsu(n);
	for (int i : v) {
		auto [u, v] = edges[i];
		r.push_back(i);
		dsu.unite(u, v);
	}
	int ans = 0;
	for (int i : on) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);	
		else ans++;
	}
	for (int i : tree) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);
	}
	return ans;
}
vector<int> get(int u, int p) {
	vector<int> ret = {u};
	for (int v : g[u]) {
		if (v == p) continue;
		auto r = get(v, u);
		for (int i : r) ret.push_back(i);
	}
	return ret;
}
int par[mxN];
void init_parent(int u, int p) {
	for (int v : g[u]) {
		if (v == p) continue;
		par[v] = u;
		init_parent(v, u);
	}
}
void dfs(int u, int p) {
	// debug("start", u, on);
	for (int v : g[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	// debug("after tree edge", u, on);
	for (int v : g[u]) {
		if (v == p) continue;
		// for each node a in subtree of v, binary search to find edges to the left subtrees
		for (int a : nodes[v]) {
			vector<int> cur;
			for (int b : nodes[u]) {
				if (ad[a][b] != -1) cur.push_back(ad[a][b]);
			}
			int L = 0;
			while (L < cur.size()) {
				int val = Myquery({});
				int lo = L, hi = cur.size();
				while (lo < hi) {
					int mid = (lo + hi) >> 1;
					int nval = Myquery(vector<int> (cur.begin() + L, cur.begin() + mid + 1));
					if (nval + reduction(vector<int> (cur.begin() + L, cur.begin() + mid + 1)) > val) {
						hi = mid;
					} else {
						lo = mid + 1;
					}
				}
				if (lo < cur.size()) {
					on.insert(cur[lo]);
				}
				L = lo + 1;
			}
		}
		for (int a : nodes[v]) {
			nodes[u].push_back(a);
		}
	}
	// debug("after subtree", u, on);
	vector<int> cur;
	for (int b : nodes[u]) {
		if (ad[u][b] != -1) cur.push_back(ad[u][b]);
	}
	int L = 0;
	while (L < cur.size()) {
		int val = Myquery({});
		int lo = L, hi = cur.size();
		while (lo < hi) {
			int mid = (lo + hi) >> 1;
			int nval = Myquery(vector<int> (cur.begin() + L, cur.begin() + mid + 1));
			if (nval + reduction(vector<int> (cur.begin() + L, cur.begin() + mid + 1)) > val) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
		if (lo < cur.size()) {
			on.insert(cur[lo]);
		}
		L = lo + 1;
	}
	nodes[u].push_back(u);
	// debug("end", u, on);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	memset(ad, -1, sizeof ad);
	n = N, m = U.size();
	for (int i = 0; i < m; i++) {
		ad[U[i]][V[i]] = ad[V[i]][U[i]] = i;
		edges.push_back({U[i], V[i]});
	}
	{
		DSU dsu(n);
		for (int i = 0; i < m; i++) {
			auto [u, v] = edges[i];
			if (dsu.unite(u, v)) {
				// cout << u << " " << v << endl;
				tree.insert(i);
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
	}
	init = query(vector<int> (tree.begin(), tree.end()));
	// debug(init);
	init_parent(0, -1);
	for (int u = 0; u < n; u++) {
		for (int v : g[u]) {
			if (v == par[u]) continue;
			bool found = false, ok = true;
			for (int vv : g[u]) {
				if (v == vv) continue;
				if (found) break;
				auto one = get(v, u), other = get(vv, u);
				for (int a : one) {
					if (found) break;
					for (int b : other) {
						if (ad[a][b] != -1) {
							int v1 = init;
							auto ntree = tree;
							ntree.erase(ad[u][vv]);
							ntree.insert(ad[a][b]);
							int v2 = query(vector<int> (ntree.begin(), ntree.end()));
							ntree.insert(ad[u][vv]);
							ntree.erase(ad[u][v]);
							int v3 = query(vector<int> (ntree.begin(), ntree.end()));
							if (v3 >= max(v1, v2)) ok = false;
							found = true;
							break;
						}
					}
				}
			}
			if (ok) on.insert(ad[u][v]);
		}
	}
	// debug(tree, on);
	dfs(0, -1);
	// debug(on);
	return vector<int> (on.begin(), on.end());
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:108:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    while (L < cur.size()) {
      |           ~~^~~~~~~~~~~~
simurgh.cpp:120:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     if (lo < cur.size()) {
      |         ~~~^~~~~~~~~~~~
simurgh.cpp:136:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  while (L < cur.size()) {
      |         ~~^~~~~~~~~~~~
simurgh.cpp:148:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   if (lo < cur.size()) {
      |       ~~~^~~~~~~~~~~~

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