# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
297735 | MoNsTeR_CuBe | Highway Tolls (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
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,0);
int mid = (left+right)/2;
for(int i = 0; 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{