Submission #1082944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082944		happypotato	Simurgh (IOI17_simurgh)	C++17	51 / 100	143 ms	4468 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 << "EDGE " << i << " ON DFS TREE" << 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) {
			// 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);
		} else {
			// 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];
			}
		}
	}

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

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