Submission #76721

#	Time	Username	Problem	Language	Result	Execution time	Memory
76721		Mamnoon_Siam	Highway Tolls (IOI18_highway)	C++17	51 / 100	404 ms	36368 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout << #s << " = " << s << endl

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 500005;

namespace {

vector<int> L, R, g[maxn], t[maxn], vis, lvl, pe, wot, where;
ll pathLen, A, B;
int S, T, tym = 0, n, m;

}

void bfs(int root) {
	queue<int> Q;
	Q.emplace(root);
	lvl[root] = 0;
	pe[root] = -1, vis[root] = 1;

	while(Q.size()) {
		int u = Q.front();
		Q.pop();
		for(int i : g[u]) {
			int v = L[i] ^ R[i] ^ u;
			if(!vis[v]) {
				vis[v] = 1;
				Q.emplace(v);
				lvl[v] = lvl[u] + 1;
				pe[v] = i;

				t[u].emplace_back(i);
				t[v].emplace_back(i);
			}
		}
	}
}

void dfs(int u) {
	vis[u] = 1;
	wot[tym] = u;
	where[u] = tym++;
	for(int i : t[u]) {
		int v = L[i] ^ R[i] ^ u;
		if(!vis[v]) {
			dfs(v);
		}
	}
}

void find_pair(int _N, std::vector<int> _U, std::vector<int> _V, int _A, int _B) {
	n = _N, L = _U, R = _V, A = _A, B = _B, m = _U.size();
	vis.assign(n, 0), lvl.assign(n, 0), pe.assign(n, 0), wot.assign(n, 0), where.assign(n, 0);

	for(int i = 0; i < m; i++) {
		g[L[i]].emplace_back(i);
		g[R[i]].emplace_back(i);
		// cout << i << " ----> " << L[i] << ' ' << R[i] << endl;
	}

	{
		vector<int> w(m);
		pathLen = ask(w) / A;
		// debug(pathLen);
	}

	int root;
	{
		int lo = 0, hi = m - 1, mid, ret = -1;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> w(m);
			for(int i = 0; i <= mid; i++) {
				w[i] = 1;
			}
			if(ask(w) != A * pathLen) {
				ret = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		root = ret == -1 ? -1 : L[ret];
	}

	// debug(root);

	bfs(root);
	fill(vis.begin(), vis.end(), 0);
	dfs(root);
	// for(int b : wot) cout << b << ' '; cout << endl;
	// for(int b : pe) cout << b << ' '; cout << endl;

	S = T = -1;

	{
		int lo = 0, hi = n - 1, mid;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> w(m, 1);
			for(int i = 0; i <= mid; i++) {
				w[pe[wot[i]]] = 0;
			}
			if(ask(w) == A * pathLen) {
				S = wot[mid];
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
	}

	{
		int lo = 0, hi = n - 1, mid;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> w(m, 1);
			for(int i = 0; i <= mid; i++) {
				w[pe[wot[i]]] = 0;
			}
			int u = S;
			while(pe[u] != -1) {
				w[pe[u]] = 1;
				u = u ^ L[pe[u]] ^ R[pe[u]];
			}
			// for(int i = 0; i < m; i++) cout << i << ' '; cout << endl;
			// for(int b : w) cout << b << ' '; cout << endl;

			// debug(ask(w));

			if(ask(w) == A * (pathLen - lvl[S]) + B * lvl[S]) {
				T = wot[mid];
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
	}
	// debug(S), debug(T);
	answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~
highway.cpp:104:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~
highway.cpp:121:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~

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