Submission #175786

#	Time	Username	Problem	Language	Result	Execution time	Memory
175786		oolimry	Highway Tolls (IOI18_highway)	C++14	100 / 100	327 ms	11056 KiB

highway

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

typedef pair<int,int> ii;
ii vis[90005];
vector<ii> adj[90005];
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size();
	vector<int> w; w.assign(m, 0);

	for(int i = 0;i < m;i++){
		adj[U[i]].push_back(ii(V[i],i));
		adj[V[i]].push_back(ii(U[i],i));
	}

	long long allLight = ask(w);
	int low = 0, high = m - 1;
	while(low < high){
		int s = (high + low) / 2;
		for(int i = 0;i < m;i++) w[i] = (i <= s);
		if(ask(w) == allLight) low = s + 1;
		else high = s; 
	}
	
	int sRoot = U[low], tRoot = V[low];
	vis[sRoot] = ii(1,0); vis[tRoot] = ii(2,0);
	queue<int> bfs; bfs.push(sRoot); bfs.push(tRoot);
	vector<int> sEdges, tEdges;
	int mid = low;
	
	while(!bfs.empty()){
		int u = bfs.front(); bfs.pop();
		for(ii v : adj[u]){
			if(vis[v.first] == ii(0,0)){
				bfs.push(v.first);
				vis[v.first] = ii(vis[u].first, vis[u].second + 1);
				if(vis[u].first == 1) sEdges.push_back(v.second);
				else tEdges.push_back(v.second);
			}
		}
	}
	
	int S = -1, T = -1;
	w.assign(m, 1); w[mid] = 0;
	for(int e : tEdges) w[e] = 0;
	low = -2, high = sEdges.size();
	while(true){
		if(low == high - 1) break;
		int s = (high + low) / 2;
		for(int i = 0;i < (int) sEdges.size();i++) w[sEdges[i]] = !(i <= s);
		if(ask(w) != allLight) low = s;
		else high = s;
	}
	
	if(high == -1) S = sRoot;
	else{
		int u = U[sEdges[high]], v = V[sEdges[high]];
		if(vis[u].second > vis[v].second) S = u;
		else S = v;
	}
	
	w.assign(m, 1); w[mid] = 0;
	for(int e : sEdges) w[e] = 0;
	low = -2, high = tEdges.size();
	while(true){
		if(low == high - 1) break;
		int s = (high + low) / 2;
		for(int i = 0;i < (int) tEdges.size();i++) w[tEdges[i]] = !(i <= s);
		if(ask(w) != allLight) low = s;
		else high = s;
	}
	
	if(high == -1) T = tRoot;
	else{
		int u = U[tEdges[high]], v = V[tEdges[high]];
		if(vis[u].second > vis[v].second) T = u;
		else T = v;
	}
	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