Submission #299991

#	Time	Username	Problem	Language	Result	Execution time	Memory
299991		square1001	Highway Tolls (IOI18_highway)	C++14	51 / 100	276 ms	9056 KiB

highway

#include "highway.h"
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
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, -1);
	dist[src] = 0;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i : G[u]) {
			if(dist[i] == -1) {
				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) {
	int M = U.size();
	if(M != N - 1) return;
	// subtask 1, 2, 3, 4 (51 points)
	vector<vector<int> > G(N);
	for(int i = 0; i < M; ++i) {
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	// step #0. find dist(depth[S], depth[T])
	int D = ask(vector<int>(M, 0)) / A;
	// step #1. find max(depth[S], depth[T])
	vector<int> depth = shortest_path(0, G);
	int ld = -1, rd = N;
	while(rd - ld > 1) {
		int md = (ld + rd) / 2;
		vector<int> w(M, 0);
		for(int i = 0; i < M; ++i) {
			if(depth[U[i]] >= md && depth[V[i]] >= md) {
				w[i] = 1;
			}
		}
		long long res = ask(w);
		if(res == 1LL * D * A) rd = md;
		else ld = md;
	}
	int sd = rd;
	// step #2. find either S or T
	vector<int> slist;
	for(int i = 0; i < M; ++i) {
		if(max(depth[U[i]], depth[V[i]]) == sd) {
			slist.push_back(i);
		}
	}
	int lid = 0, rid = slist.size();
	while(rid - lid > 1) {
		int mid = (lid + rid) / 2;
		vector<int> w(M, 0);
		for(int i = 0; i < mid; ++i) {
			w[slist[i]] = 1;
		}
		long long res = ask(w);
		if(res == 1LL * D * A) lid = mid;
		else rid = mid;
	}
	int S = (depth[U[slist[lid]]] > depth[V[slist[lid]]] ? U[slist[lid]] : V[slist[lid]]);
	// step #3. find both S and T
	vector<int> dist = shortest_path(S, G);
	vector<int> tlist;
	for(int i = 0; i < M; ++i) {
		if(max(dist[U[i]], dist[V[i]]) == D) {
			tlist.push_back(i);
		}
	}
	lid = 0, rid = tlist.size();
	while(rid - lid > 1) {
		int mid = (lid + rid) / 2;
		vector<int> w(M, 0);
		for(int i = 0; i < mid; ++i) {
			w[tlist[i]] = 1;
		}
		long long res = ask(w);
		if(res == 1LL * D * A) lid = mid;
		else rid = mid;
	}
	int T = (dist[U[tlist[lid]]] > dist[V[tlist[lid]]] ? U[tlist[lid]] : V[tlist[lid]]);
	answer(S, T);
}

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