Submission #263227

#	Time	Username	Problem	Language	Result	Execution time	Memory
263227		UserIsUndefined	Highway Tolls (IOI18_highway)	C++14	0 / 100	24 ms	3740 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

int depth ;

vector<pair<int,int>> adj[90005];
vector<int> can;

void dfs(int v , int dep, int p, int idx){
    if (dep == depth){
        can.push_back(idx);
        return;
    }


    for (pair<int,int> e : adj[v]){
        if (e.first != p){
            dfs(e.first, dep + 1 , v, e.second);
        }
    }

}


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int m = V.size();

    vector<int> ans;

    vector<int> test(m , 0);



    long long li = ask(test);

    depth = li/A;




    for (int i = 0 ; i < m ; i++){
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }



    dfs(0, 0 , -1, -1);



//    for (int cand : can){
//        cout << "This is cand" << cand << endl;
//    }


    int low = 0;
    int high = can.size() - 1;

    while(low <= high){
        int mid = (low + high)/2;

        vector<int> call(m);

        for (int i = low ; i <= mid ; i++){
            call[can[i]] = 1;
        }

        long long an = ask(call);

        if (an - B + A == li){
            high = mid;
        }
        else {
            low = mid + 1;
        }




    }





    answer(0 , low - 1);


}

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