Submission #297737

#	Time	Username	Problem	Language	Result	Execution time	Memory
297737		MoNsTeR_CuBe	Highway Tolls (IOI18_highway)	C++17	45 / 100	216 ms	21060 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){
    	if(left == right){
    		ans.push_back(EdgeToNode[index[left]]);
    		return;
    	}
    	vector< int > toAsk(M,0);
    	int mid = (left+right)/2;
    	for(int i = 0; i<= mid; i++){
    		toAsk[index[i]] = 1;
    		//cout << EdgeToNode[index[i]] << ' ';
    	}
    	//cout << endl;
    	long long 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+1);
      dfs(0, -1, index, Graph, curr,N, EdgeToNode);
      vector< int > ans;
      vector< int > toAsk(M);
      long long 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,N,EdgeToNode);
      //cout << "N" << endl;
      search(0,M-1, M,ans,EdgeToNode,index, mark);
      //cout << ans[1] << endl;
      assert((int)ans.size() == 2);
      answer(ans[0], ans[1]);
    }

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