oj.uz

Submission #108902

# Submission time Handle Problem Language Result Execution time Memory
108902 2019-05-02T13:51:55 Z Noam527 Simurgh (IOI17_simurgh) C++17
0 / 100
 288 ms 6524 KB 
#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];
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 = v, tmp;
	if (dep[u] > dep[v]) swap(u, 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 " << aa.first << " " << aa.second << ", " << 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;
		}
		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, g[s][i].to);
		rr[nxt++] = g[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, g[s].size());
	if (OO) cout << "calc " << s << ", tot " << tot << '\n';
	int lo = 1, hi = (int)g[s].size(), mid;
	for (int i = 1; i <= tot; i++) {
		hi = (int)g[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 << ", " << g[s][lo - 1].to << ", index " << g[s][lo - 1].i << '\n';
		rtn.push_back(g[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 < n - 1; i++) value[i] = -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));
		value[i] = -1;
	}
	dfs();
	if (OO) {
		cout << "my spanning tree\n";
		for (const auto &i : tree) cout << 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

simurgh.cpp: In function 'void process(std::pair<int, int>, int)':
simurgh.cpp:80:43: warning: unused variable 'tmp' [-Wunused-variable]
  int u = aa.first, v = aa.second, vv = v, tmp;
                                           ^~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:196:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << i << " "; cout << '\n';
   ^~~
simurgh.cpp:196: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:206:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << i << " "; cout << '\n';
   ^~~
simurgh.cpp:206: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:208:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : tree) cout << value[i] << " "; cout << '\n';
   ^~~
simurgh.cpp:208: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 153 ms 4616 KB correct
4 Correct 272 ms 6520 KB correct
5 Correct 270 ms 6392 KB correct
6 Correct 264 ms 6524 KB correct
7 Correct 232 ms 6520 KB correct
8 Correct 267 ms 6520 KB correct
9 Correct 267 ms 6520 KB correct
10 Correct 288 ms 6520 KB correct
11 Correct 257 ms 6520 KB correct
12 Correct 285 ms 6520 KB correct
13 Incorrect 3 ms 384 KB WA in grader: NO
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -