Submission #1209440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209440		Aviansh	Highway Tolls (IOI18_highway)	C++20	5 / 100	56 ms	10732 KiB

highway

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

using namespace std;

vector<int>edgeorder;
int m;

void dfs(int st, vector<array<int,2>>g[], int p[], int par){
    p[st]=par;
    for(array<int,2>e:g[st]){
        if(e[0]==par)
            continue;
        edgeorder.push_back(e[1]);
        dfs(e[0],g,p,st);
    }
}

int check(int x){
    //x is included
    vector<int>w(m);
    for(int i = 0;i<=x;i++){
        w[edgeorder[i]]=1;
    }
    return ask(w);
}

void find_pair(int n, vector<int> U, vector<int> V, int a, int b) {
    vector<array<int,2>>g[n];
    m = U.size();
    assert(m==n-1);
    for(int i = 0;i<m;i++){
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }
    //assuming s is 0
    //finding other
    edgeorder.clear();
    int p[n];
    dfs(0,g,p,-1);
    int lo = 0;
    int hi = edgeorder.size()-1;
    vector<int>w(m);
    int bas = ask(w);
    int ecn = bas/a;
    int target = ecn*b;
    while(lo<hi){
        int mid = (lo+hi)/2;
        if(check(mid)<target){
            lo=mid+1;
        }
        else{
            hi=mid;
        }
    }
    lo=edgeorder[lo];
    if(U[lo]==p[V[lo]]){
        answer(0,V[lo]);
    }
    else{
        answer(0,U[lo]);
    }
}

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