Submission #1209453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209453		Aviansh	Highway Tolls (IOI18_highway)	C++20	51 / 100	79 ms	15332 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);
    }
}

long long 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);
    long long bas = ask(w);
    long long ecn = bas/a;
    long long target = ecn*b;
    while(lo<hi){
        int mid = (lo+hi)/2;
        if(check(mid)<target){
            lo=mid+1;
        }
        else{
            hi=mid;
        }
    }
    lo=edgeorder[lo];
    int s;
    if(U[lo]==p[V[lo]]){
        s=V[lo];
    }
    else{
        s=U[lo];
    }
    //s discovered now same thing as last time will give t.

    edgeorder.clear();
    dfs(s,g,p,-1);
    lo=0;
    hi=edgeorder.size()-1;
    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(s,V[lo]);
    }
    else{
        answer(s,U[lo]);
    }
}

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