Submission #297607

#	Time	Username	Problem	Language	Result	Execution time	Memory
297607		MoNsTeR_CuBe	Highway Tolls (IOI18_highway)	C++17	5 / 100	215 ms	22216 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, int mark){
	if(left == right){
		ans.push_back(EdgeToNode[index[left]]);
		return;
	}
	vector< int > toAsk(M);
	int mid = (left+right)/2;
	for(int i = left; i<= mid; i++){
		toAsk[index[i]] = 1;
		//cout << EdgeToNode[index[i]] << ' ';
	}
	//cout << endl;
	int rep = ask(toAsk);
	if(rep > mark){
		search(left, mid, M, ans,EdgeToNode,index, mark);
	}else{
		search(mid+1, right, M, ans,EdgeToNode,index, mark);
	}
}

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);
  int mark = ask(toAsk);
  search(0,M-1, M,ans,EdgeToNode,index, mark);
  //cout << ans[0] << endl;
  curr = 0;
  dfs(ans[0],-1,index,Graph,curr,-1,EdgeToNode);
  //cout << "N" << endl;
  search(0,M-1, M,ans,EdgeToNode,index, mark);
  //cout << ans[1] << endl;
  
  answer(ans[0], ans[1]);
}

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