Submission #301644

#	Time	Username	Problem	Language	Result	Execution time	Memory
301644		square1001	Highway Tolls (IOI18_highway)	C++14	100 / 100	352 ms	15264 KiB

highway

#include "highway.h"
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
vector<int> shortest_path(int src, const vector<vector<int> > &G) {
	int N = G.size();
	queue<int> que;
	que.push(src);
	vector<int> dist(N, inf);
	dist[src] = 0;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i : G[u]) {
			if(dist[i] == inf) {
				dist[i] = dist[u] + 1;
				que.push(i);
			}
		}
	}
	return dist;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	// subtask 1, 2, 3, 4, 5, 6 (90 points)
	// step #0. calculate basic distance
	int M = U.size();
	int D = ask(vector<int>(M, 0)) / A;
	// step #1. binary search connectivity
	int lt = -1, rt = N;
	while(rt - lt > 1) {
		int mt = (lt + rt) >> 1;
		if(lt == -1 && rt == N && N >= 65535) mt = 65534;
		vector<int> w(M);
		for(int i = 0; i < M; ++i) {
			w[i] = (U[i] <= mt && V[i] <= mt ? 0 : 1);
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rt = mt;
		else lt = mt;
	}
	int cutvert = rt;
	// step #2. find either S or T
	vector<vector<int> > G2(cutvert + 1);
	for(int i = 0; i < M; ++i) {
		if(U[i] <= cutvert && V[i] <= cutvert) {
			G2[U[i]].push_back(V[i]);
			G2[V[i]].push_back(U[i]);
		}
	}
	vector<int> dc = shortest_path(cutvert, G2);
	vector<int> perm(cutvert + 1);
	for(int i = 0; i <= cutvert; ++i) {
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) { return dc[i] != dc[j] ? dc[i] < dc[j] : i < j; });
	vector<int> iperm(cutvert + 1);
	for(int i = 0; i <= cutvert; ++i) {
		iperm[perm[i]] = i;
	}
	int ls = -1, rs = cutvert + 1;
	while(rs - ls > 1) {
		int ms = (ls + rs) >> 1;
		vector<int> w(M);
		for(int i = 0; i < M; ++i) {
			if(U[i] <= cutvert && V[i] <= cutvert && iperm[U[i]] <= ms && iperm[V[i]] <= ms) {
				w[i] = 0;
			}
			else {
				w[i] = 1;
			}
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rs = ms;
		else ls = ms;
	}
	int S = perm[rs];
	// step #3. find both S and T
	vector<vector<int> > G3(cutvert + 1);
	for(int i = 0; i < M; ++i) {
		if(U[i] <= cutvert && V[i] <= cutvert && iperm[U[i]] <= iperm[S] && iperm[V[i]] <= iperm[S]) {
			G3[U[i]].push_back(V[i]);
			G3[V[i]].push_back(U[i]);
		}
	}
	vector<int> ds = shortest_path(S, G3);
	vector<int> perm2;
	for(int i = 0; i <= cutvert; ++i) {
		if(iperm[i] <= iperm[S]) {
			perm2.push_back(i);
		}
	}
	sort(perm2.begin(), perm2.end(), [&](int i, int j) { return ds[i] != ds[j] ? ds[i] < ds[j] : i < j; });
	vector<int> iperm2(cutvert + 1);
	for(int i = 0; i < int(perm2.size()); ++i) {
		iperm2[perm2[i]] = i;
	}
	int lg = -1, rg = perm2.size() + 1;
	while(rg - lg > 1) {
		int mg = (lg + rg) >> 1;
		vector<int> w(M);
		for(int i = 0; i < M; ++i) {
			if(U[i] <= cutvert && V[i] <= cutvert && iperm2[U[i]] <= mg && iperm2[V[i]] <= mg) {
				w[i] = 0;
			}
			else {
				w[i] = 1;
			}
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rg = mg;
		else lg = mg;
	}
	int T = perm2[rg];
	answer(S, T);
}

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