Submission #1082979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082979		happypotato	Simurgh (IOI17_simurgh)	C++17	100 / 100	292 ms	6388 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
vector<vector<pii>> adj;
vector<pii> par;
vector<int> dep;
vector<bool> vis;
vector<bool> ontree;
vector<int> ans;
int n, m;
void dfstree(int u = 1, int pp = 0, int d = 1) {
	dep[u] = d;
	vis[u] = true;
	for (pii v : adj[u]) {
		if (vis[v.ff]) continue;
		par[v.ff] = {u, v.ss};
		ontree[v.ss] = true;
		dfstree(v.ff, u, d + 1);
	}
}
set<int> qry;
void del(int x) { qry.erase(qry.find(x)); }
void add(int x) { qry.insert(x); }
int ask() {
	vector<int> r;
	for (int x : qry) r.pb(x);
	return count_common_roads(r);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N; m = (int)(U.size());
	adj.resize(n + 1);
	par.clear(); par.resize(n + 1, make_pair(0, 0));
	dep.clear(); dep.resize(n + 1, 0);
	vis.clear(); vis.resize(n + 1, false);
	ontree.clear(); ontree.resize(m, false);
	ans.clear(); ans.resize(m, -1);
	for (int i = 0; i < m; i++) {
		U[i]++; V[i]++;
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}

	dfstree();
	for (int i = 0; i < m; i++) {
		if (ontree[i]) {
			// cerr << "DFS TREE: " << U[i] << ' ' << V[i] << endl;
			qry.insert(i);
		}
	}
	int INIT = ask();
	// cerr << INIT << endl;

	for (int i = 0; i < m; i++) {
		if (dep[U[i]] > dep[V[i]]) swap(U[i], V[i]);
		if (ontree[i]) continue;
		vector<int> chain;
		int cur = V[i];
		while (cur != U[i]) {
			chain.pb(par[cur].ss);
			cur = par[cur].ff;
		}
		// cerr << "edge " << i << ": ";
		// for (int x : chain) cerr << x << ' ';
		// cerr << endl;
		int len = chain.size();
		int cnt = 0;
		for (int x : chain) cnt += (ans[x] != -1);
		if (cnt == 0) {
			// everything unknown: query everything
			vector<int> res;
			add(i);
			for (int x : chain) {
				del(x);
				res.pb(ask());
				add(x);
			}
			del(i);
			// cannot be all 1s, so if all equal assign 0s
			int maxi = INIT;
			for (int x : res) maxi = max(maxi, x);
			// cerr << "checking ";
			// for (int x : chain) cerr << x << ' ';
			// cerr << ", maxi = " << maxi << endl;
			ans[i] = maxi - INIT;
			for (int i = 0; i < len; i++) {
				ans[chain[i]] = maxi - res[i];
			}
		} else if (cnt < len) {
			// more than one known: query everything else
			pii known = {-1, -1};
			for (int x : chain) {
				if (ans[x] != -1) {
					known = {x, ans[x]};
					break;
				}
			}
			// query everything else except for this, calculate expected sum
			del(known.ff); add(i);
			int TOT = ask() + known.ss;
			add(known.ff);
			// calcuate i from TOT and INIT
			ans[i] = TOT - INIT;
			// erase every unknown edge and calculate
			for (int x : chain) {
				if (ans[x] != -1) continue;
				del(x);
				ans[x] = TOT - ask();
				add(x);
			}
			del(i);
		}
	}
	for (int i = 0; i < m; i++) {
		// check for bridges
		if (ontree[i] && ans[i] == -1) ans[i] = 1;
	}

	vector<int> edges;
	auto test = [&](int lb, int rb) -> bool {
		int expect = INIT;
		for (int i = lb; i <= rb; i++) {
			int u = U[edges[i]], v = V[edges[i]];
			// u is ancestor of v -> remove {v, par[v]}
			del(par[v].ss); expect -= ans[par[v].ss];
			add(edges[i]);
			// cerr << u << ' ' << v << ' ' << edges[i] << ": ";
			// cerr << par[v].ff << ' ' << par[v].ss << ' ' << ans[par[v].ss] << endl;
		}
		bool ret = (ask() > expect);
		for (int i = lb; i <= rb; i++) {
			int u = U[edges[i]], v = V[edges[i]];
			add(par[v].ss);
			del(edges[i]);
		}
		return ret;
	};

	// query remaining edges
	for (int u = 1; u <= n; u++) {
		edges.clear();
		for (pii v : adj[u]) {
			if (dep[v.ff] > dep[u] && ans[v.ss] == -1) edges.pb(v.ss);
		}
		// cerr << "edges: ";
		// for (int x : edges) cerr << x << ' ';
		// cerr << endl;
		if (edges.empty()) continue;
		while (test(0, (int)(edges.size()) - 1)) {
			int lb = 0, rb = (int)(edges.size()) - 1;
			while (lb < rb) {
				int mid = (lb + rb) >> 1;
				if (test(lb, mid)) rb = mid;
				else lb = mid + 1;
			}
			// edges[lb] is answer
			ans[edges[lb]] = 1;
			edges.erase(edges.begin() + lb);
		}
	}

	vector<int> fin;
	for (int i = 0; i < m; i++) {
		if (ans[i] == 1) fin.pb(i);
	}
	// cerr << "ANSWER: ";
	// for (int x : fin) cerr << x << ' ';
	// cerr << endl;
	return fin;
}

Compilation message (stderr)

simurgh.cpp: In lambda function:
simurgh.cpp:126:8: warning: unused variable 'u' [-Wunused-variable]
  126 |    int u = U[edges[i]], v = V[edges[i]];
      |        ^
simurgh.cpp:135:8: warning: unused variable 'u' [-Wunused-variable]
  135 |    int u = U[edges[i]], v = V[edges[i]];
      |        ^

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