Submission #108912

#	Time	Username	Problem	Language	Result	Execution time	Memory
108912		Noam527	Simurgh (IOI17_simurgh)	C++17	100 / 100	250 ms	7928 KiB

simurgh

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

int count_common_roads(const vector<int>& r);

int ask(const vector<int> &r) {
	return count_common_roads(r);
}

struct edge {
	int to, i;
	edge() {}
	edge(int tt, int ii) {
		to = tt;
		i = ii;
	}
};
struct dsu {
	int n;
	vector<int> p, r;
	dsu() {}
	dsu(int sz) {
		n = sz;
		p.resize(n);
		r.resize(n);
		clear();
	}
	void clear() {
		for (int i = 0; i < n; i++) {
			p[i] = i;
			r[i] = 0;
		}
	}
	int find(int x) {
		return x == p[x] ? x : p[x] = find(p[x]);
	}
	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return false;
		if (r[x] < r[y]) p[x] = y;
		else {
			p[y] = x;
			if (r[x] == r[y]) r[x]++;
		}
		return true;
	}
};

const int mxn = 505, mxm = 125000;

int n, m;
vector<edge> g[mxn], gg[mxn]; // in gg, only "directed" edges
int vis[mxn], par[mxn], pare[mxn];
int dep[mxn];
vector<int> tree;
int org;
int value[mxm];

void dfs(int v = 0, int d = 0) {
	vis[v] = 1;
	dep[v] = d;
	for (const auto &i : g[v])
		if (!vis[i.to]) {
			par[i.to] = v;
			pare[i.to] = i.i;
			tree[i.to - 1] = i.i;
			dfs(i.to, 1 + d);
		}
}

void process(pair<int, int> aa, int i) {
	int u = aa.first, v = aa.second, vv, tmp;
	if (dep[u] > dep[v]) swap(u, v);
	vv = v;
	if (tree[v - 1] == i) return;
	bool found = false;
	int good = -1;
	while (vv != u) {
		if (value[pare[vv]] == -1) {
			found = true;
			break;
		}
		vv = par[vv];
	}
	if (OO) cout << "processing edge " << u << " " << v << ", " << found << '\n';
	if (!found) return;
	vv = v;
	while (vv != u) {
		if (value[pare[vv]] != -1) {
			good = vv;
			break;
		}
		vv = par[vv];
	}
	int curedge;
	if (good == -1) {
		vv = v;
		found = false;
		while (vv != u) {
			swap(tree[vv - 1], i);
			int x = ask(tree);
			swap(tree[vv - 1], i);
			if (x != org) {
				found = true;
				if (x < org) curedge = 0;
				else curedge = 1;
				break;
			}
			vv = par[vv];
		}
		if (!found) curedge = 0;
	}
	else {
		swap(tree[good - 1], i);
		int x = ask(tree);
		swap(tree[good - 1], i);
		if (x < org) curedge = 0;
		else if (x > org) curedge = 1;
		else curedge = value[pare[vv]];
	}
	if (OO) cout << "curedge " << curedge << '\n';
	vv = v;
	while (vv != u) {
		if (value[pare[vv]] == -1) {
			swap(tree[vv - 1], i);
			int x = ask(tree);
			swap(tree[vv - 1], i);
			if (x < org) value[pare[vv]] = 1;
			else if (x > org) value[pare[vv]] = 0;
			else value[pare[vv]] = curedge;
			if (OO) {
				cout << "so, value of " << pare[vv] << " is " << value[pare[vv]] << '\n';
			}
		}
		vv = par[vv];
	}
}

dsu ds;
vector<int> rr;

int query(int s, int pre) {
	ds.clear();
	int nxt = 0;
	for (int i = 0; i < pre; i++) {
		ds.unite(s, gg[s][i].to);
		rr[nxt++] = gg[s][i].i;
	}
	int ans = 0;
	for (int i = 1; i < n; i++)
		if (ds.unite(i, par[i])) {
			ans -= value[tree[i - 1]];
			rr[nxt++] = tree[i - 1];
		}
	//if (OO) cout << "query " << s << " " << pre << ", ans " << ans << '\n';
	return ans + ask(rr);
}

vector<int> calc(int s) {
	vector<int> rtn;
	int tot = query(s, gg[s].size());
	if (OO) cout << "calc " << s << ", tot " << tot << '\n';
	if (tot == 0) return{};
	int lo = 1, hi = (int)gg[s].size(), mid;
	for (int i = 1; i <= tot; i++) {
		hi = (int)gg[s].size();
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (query(s, mid) < i) lo = mid + 1;
			else hi = mid;
		}
		if (OO) cout << "edge " << i << " is " << s << ", " << gg[s][lo - 1].to << ", index " << gg[s][lo - 1].i << '\n';
		rtn.push_back(gg[s][lo - 1].i);
	}
	return rtn;
}

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n = N;
	m = u.size();
	tree.resize(n - 1);
	ds = dsu(n);
	rr.resize(n - 1);
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back(edge(v[i], i));
		g[v[i]].push_back(edge(u[i], i));
		gg[min(u[i], v[i])].push_back(edge(max(u[i], v[i]), i));
		value[i] = -1;
	}
	dfs();
	if (OO) {
		cout << "my spanning tree\n";
		for (const auto &i : tree) cout << i << " "; cout << '\n';
		cout << "par: ";
		for (const auto &i : tree) cout << par[i] << " "; cout << '\n';
		cout << "par: ";
		for (const auto &i : tree) cout << pare[i] << " "; cout << '\n';
	}
	org = ask(tree);
	for (int i = 0; i < m; i++) {
		process(make_pair(u[i], v[i]), i);
	}
	for (const auto &i : tree)
		if (value[i] == -1) value[i] = 1; // bridge
	if (OO) {
		cout << "my spanning tree\n";
		for (const auto &i : tree) cout << i << " "; cout << '\n';
		cout << "with values\n";
		for (const auto &i : tree) cout << value[i] << " "; cout << '\n';
	}

	vector<int> tmp, ans(m, 0);
	for (int i = 0; i < n; i++) {
		tmp = calc(i);
		for (const auto &j : tmp) ans[j] = 1;
	}
	tmp.clear();
	for (int i = 0; i < m; i++)
		if (ans[i])
			tmp.push_back(i);
	return tmp;
}

Compilation message (stderr)

simurgh.cpp: In function 'void process(std::pair<int, int>, int)':
simurgh.cpp:80:39: warning: unused variable 'tmp' [-Wunused-variable]
  int u = aa.first, v = aa.second, vv, tmp;
                                       ^~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:201:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << i << " "; cout << '\n';
   ^~~
simurgh.cpp:201:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : tree) cout << i << " "; cout << '\n';
                                                ^~~~
simurgh.cpp:203:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << par[i] << " "; cout << '\n';
   ^~~
simurgh.cpp:203:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : tree) cout << par[i] << " "; cout << '\n';
                                                     ^~~~
simurgh.cpp:205:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << pare[i] << " "; cout << '\n';
   ^~~
simurgh.cpp:205:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : tree) cout << pare[i] << " "; cout << '\n';
                                                      ^~~~
simurgh.cpp:215:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << i << " "; cout << '\n';
   ^~~
simurgh.cpp:215:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : tree) cout << i << " "; cout << '\n';
                                                ^~~~
simurgh.cpp:217:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << value[i] << " "; cout << '\n';
   ^~~
simurgh.cpp:217:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : tree) cout << value[i] << " "; cout << '\n';
                                                       ^~~~

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