Submission #108106

#	Time	Username	Problem	Language	Result	Execution time	Memory
108106		Noam527	Highway Tolls (IOI18_highway)	C++17	100 / 100	354 ms	12208 KiB

highway

#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;

void answer(int s, int t);

ll ask(const vector<int> &w);

struct edge {
	int to, i;
	edge() {}
	edge(int tt, int ii) {
		to = tt;
		i = ii;
	}
};

vector<int> w;
vector<int> ord;
vector<int> special;

int n, m;
ll d;
vector<vector<edge>> g;
vector<int> vis, dep;

int crit;

ll f(int x) {
	for (int i = 0; i < x; i++) w[ord[i]] = 0;
	for (int i = x; i < ord.size(); i++) w[ord[i]] = 1;
	return ask(w);
}

void bfs(int v) {
	ord.clear();
	vis.resize(n, 0);
	dep.resize(n, 0);
	vis[v] = 1;
	queue<int> q;
	q.push(v);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (const auto &i : g[x])
			if (!vis[i.to]) {
				dep[i.to] = dep[x] + 1;
				ord.push_back(i.i);
				vis[i.to] = 1;
				q.push(i.to);
			}
	}
}
void dfs(int v) {
	vis[v] = 1;
	for (const auto &i : g[v])
		if (!vis[i.to] && w[i.i] == 0) {
			special[i.i] = 1;
			dfs(i.to);
		}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	if (N == 2) {
		answer(0, 1);
		return;
	}
	n = N;
	g.resize(n);
	m = U.size();
	w.resize(m);
	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));
	}
	for (auto &i : w) i = 0;
	d = ask(w);
	if (OO) cout << "d = " << d << '\n';
	int lo, hi, mid;

	// 1: find edge on shortest path
	ord.resize(m);
	for (int i = 0; i < m; i++) ord[i] = i;
	lo = 0, hi = m - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	crit = lo;
	if (OO) cout << "critical edge index " << crit << ", (" << U[crit] << ", " << V[crit] << ")\n";
	// 2: root at 1 end of the edge, and bsearch in the subtree of the other for S/T
	for (auto &i : w) i = 1;
	// prioritize the critical edge
	for (auto &i : g[U[crit]])
		if (i.i == crit) {
			swap(i, g[U[crit]][0]);
		}
	bfs(U[crit]);
	for (auto &i : ord) w[i] = 0;

	// determine all edges in the subtree of the other end
	for (auto &i : vis) i = 0;
	vis[U[crit]] = 1;
	special.resize(m, 0);
	special[crit] = 1;
	dfs(V[crit]);
	vector<int> ord1, ord2;
	for (const auto &i : ord)
		if (special[i])
			ord1.push_back(i);
		else
			ord2.push_back(i);

	if (OO) {
		cout << "rooted at " << U[crit] << '\n';
		cout << "bfs: ";
		for (const auto &i : ord) cout << i << " "; cout << '\n';
		cout << "ord1: ";
		for (const auto &i : ord1) cout << i << " "; cout << '\n';
		cout << "ord2: ";
		for (const auto &i : ord2) cout << i << " "; cout << '\n';
		cout << "dep: ";
		for (const auto &i : dep) cout << i << " "; cout << '\n';
	}

	// bsearch in the subtree
	ord = ord1;
	lo = 0, hi = (int)ord.size() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	int S, T;
	if (OO) {
		cout << "first bsearch yields edge " << ord[lo] << '\n';
	}
	if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) S = U[ord[lo]];
	else S = V[ord[lo]];
	if (OO) cout << "resulting in S = " << S << '\n';

	if ((ll)A * dep[S] == d) {
		T = U[crit];
		answer(S, T);
		return;
	}

	// bsearch on everything else
	for (auto &i : ord1) w[i] = 0;
	ord = ord2;
	lo = 0, hi = (int)ord.size() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	if (OO) {
		cout << "second bsearch yields edge " << ord[lo] << '\n';
	}
	if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) T = U[ord[lo]];
	else T = V[ord[lo]];
	if (OO) cout << "resulting in T = " << T << '\n';

	answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'll f(int)':
highway.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = x; i < ord.size(); i++) w[ord[i]] = 1;
                  ~~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:125:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ord) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:125:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ord) cout << i << " "; cout << '\n';
                                               ^~~~
highway.cpp:127:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ord1) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:127:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ord1) cout << i << " "; cout << '\n';
                                                ^~~~
highway.cpp:129:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ord2) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:129:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ord2) cout << i << " "; cout << '\n';
                                                ^~~~
highway.cpp:131:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : dep) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:131:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : dep) cout << i << " "; cout << '\n';
                                               ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31