Submission #175505

#	Time	Username	Problem	Language	Result	Execution time	Memory
175505		oolimry	Highway Tolls (IOI18_highway)	C++14	6 / 100	202 ms	8892 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, 1);
    
    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 allHeavy = 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] = !(low <= i && i <= s);
		if(ask(w) == allHeavy) 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;
	
	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, T;
	w.assign(m, 1);
	
	low = 0, 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) != allHeavy) low = s;
		else high = s;
	}
	
	if(low == 0) S = sRoot;
	else{
		int u = U[sEdges[low]], v = V[sEdges[low]];
		if(vis[u].second > vis[v].second) S = u;
		else S = v;
	}
	
	w.assign(m, 1);
	low = 0, 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) != allHeavy) low = s;
		else high = s;
	}
	
	if(low == 0) T = tRoot;
	else{
		int u = U[tEdges[low]], v = V[tEdges[low]];
		if(vis[u].second > vis[v].second) T = u;
		else T = v;
	}
	
	//cout << S << " " << T << "\n";
	answer(S, T);
}

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