Submission #995516

#	Time	Username	Problem	Language	Result	Execution time	Memory
995516		hirayuu_oj	Highway Tolls (IOI18_highway)	C++17	51 / 100	85 ms	10240 KiB

highway

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
ll LINF=(1LL<<61)-1;
ll MINF=1LL<<40;
int INF=INT_MAX>>1;

template<class S>
void out_vector(vector<S> v){
    for(S i:v)cerr<<i<<" ";
    cerr<<"\n";
}
#include "highway.h"

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M=U.size();
    ll dist=ask(vector<int>(M,0))/A;
    int ok=0,ng=M;
    while(ng-ok>1){
        int mid=(ok+ng)/2;
        vector<int> ques(M,0);
        rep2(i,ok,mid)ques[i]=1;
        if(ask(ques)==dist*A){
            ok=mid;
        }
        else{
            ng=mid;
        }
    }
    vector<vector<pair<int,int>>> tree(N);
    rep(i,N){
        if(i!=ok){
            tree[U[i]].emplace_back(V[i],i);
            tree[V[i]].emplace_back(U[i],i);
        }
    }
    int curs=U[ok],curt=V[ok];
    vector<int> sdis(N,-1);
    vector<int> par(N,-1);
    vector<int> which(N,-1);
    sdis[curs]=0;
    sdis[curt]=0;
    int sad;
    {
        stack<int> vert;
        vert.push(curt);
        vert.push(curs);
        vector<int> ques(M,0);
        int flg=1;
        while(!vert.empty()){
            int pos=vert.top();
            if(pos==curt)flg=0;
            which[pos]=flg;
            vert.pop();
            for(auto &[t,i]:tree[pos]){
                if(sdis[t]==-1){
                    ques[i]=flg;
                    par[t]=i;
                    sdis[t]=sdis[pos]+1;
                    vert.push(t);
                }
            }
        }
        sad=(ask(ques)-dist*A)/(B-A);
        vector<int> kouho;
        rep(i,N){
            if(which[i]==1&&sad==sdis[i]){
                kouho.emplace_back(i);
            }
        }
        ok=0,ng=kouho.size();
        while(ng-ok>1){
            int mid=(ok+ng)/2;
            vector<int> ques(M,0);
            rep2(i,ok,mid)ques[par[kouho[i]]]=1;
            if(ask(ques)==dist*A){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        curs=kouho[ok];
    }
    {
        sad=dist-1-sad;
        vector<int> kouho;
        rep(i,N){
            if(which[i]==0&&sad==sdis[i]){
                kouho.emplace_back(i);
            }
        }
        ok=0,ng=kouho.size();
        while(ng-ok>1){
            int mid=(ok+ng)/2;
            vector<int> ques(M,0);
            rep2(i,ok,mid)ques[par[kouho[i]]]=1;
            if(ask(ques)==dist*A){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        curt=kouho[ok];
    }
    answer(curs,curt);
}

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