Submission #263247

#	Time	Username	Problem	Language	Result	Execution time	Memory
263247		UserIsUndefined	Highway Tolls (IOI18_highway)	C++14	12 / 100	130 ms	8580 KiB

highway

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

using namespace std;

int depth ;

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

void dfs(int v , int dep, int p, int idx){
//    cout << v << " " << dep << " " << p << " " << idx << " here "<<  endl;
    depthh[v] = dep;
    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;

//    cout << "dipth" << depth << endl;


    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;
//         cout << low  << " h " << high << endl;
        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;
        }




    }

    if (low > high)low--;
    int ed = can[low];

    int s = -1;

    if (depthh[U[ed]] == depth){
        s = U[ed];
    }
    else {
        s = V[ed];
    }





    answer(0 , s);


}

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