Submission #297740

#	Time	Username	Problem	Language	Result	Execution time	Memory
297740		MoNsTeR_CuBe	Highway Tolls (IOI18_highway)	C++17	12 / 100	181 ms	20344 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
 
void dfs(int node, int parent, vector< int > &index, vector< vector< pair<int,int> > > &Graph, int &curr, int lastEdge, vector< int > &EdgeToNode){
 
	for(auto a: Graph[node]){
		if(a.first == parent) continue;
		dfs(a.first, node, index, Graph, curr, a.second, EdgeToNode);
	}	
	index[curr++] = lastEdge;
	if(lastEdge != -1) EdgeToNode[lastEdge] = node;
}
 
void search(int left, int right, int M, vector< int > &ans, vector< int > &EdgeToNode, vector< int > &index, long long mark, int leftToFind){
	if(left == right){
		ans.push_back(EdgeToNode[index[left]]);
		//cout << "FOUND " << EdgeToNode[index[left]] << endl;
		return;
	}
	//cout << left << ' ' << right << endl;
	vector< int > toAsk(M);
	int mid = (left+right)/2;
	//cout << "HERE " << endl;
	for(int i = left; i<= mid; i++){
		//cout << index[i] << ' ';
		//cout << EdgeToNode[index[i]] << ' ';
		toAsk[index[i]] = 1;
	}
	//cout << endl;
	//cout << endl;
	long long rep = ask(toAsk);
	//cout << "REP " << rep << endl;
	if(rep > mark){
		//cout << "YEP " << endl;
		
		if(leftToFind == 1){
			search(left, mid, M, ans,EdgeToNode,index, mark,leftToFind);
			return;
		} 
		for(int i = left; i<= mid; i++){
			toAsk[index[i]] = 0;
		}
		for(int i = mid+1; i <= right; i++){
			toAsk[index[i]] = 1;
		}
		rep = ask(toAsk);
		if(rep > mark){
			search(left, mid, M, ans,EdgeToNode,index, mark,1);
			search(mid+1, right, M, ans,EdgeToNode,index, mark,1);
		}else{
			search(left, mid, M, ans,EdgeToNode,index, mark,1);
		}
	}else{
		search(mid+1, right, M, ans,EdgeToNode,index, mark,leftToFind);
	}
	
	
}
 
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  vector< vector< pair<int, int> > > Graph(N);
  for(int i = 0; i < M; i++){
		Graph[U[i]].push_back({V[i],i});
		Graph[V[i]].push_back({U[i],i});
  }
  
  int curr = 0;
  vector< int > index(N);
  vector< int > EdgeToNode(M);
  dfs(0, -1, index, Graph, curr,-1, EdgeToNode);
  vector< int > ans;
  
  vector< int > toAsk(M);
  long long mark = ask(toAsk);
  //cout << "OK" << endl;
  search(0,M-1, M,ans,EdgeToNode,index, mark,1);
  
  //cout << "OK" << endl;
  
  if(ans.size() == 1){
	ans.push_back(0);
  }
  //cout << ans[0] << ' ' << ans[1] << endl;
  answer(ans[0], ans[1]);
}

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