Submission #1291222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291222		Math4Life2020	Highway Tolls (IOI18_highway)	C++20	100 / 100	474 ms	30484 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
mt19937_64 gen;


pair<vector<ll>,vector<ll>> dijk(ll src, ll N, vector<int> U, vector<int> V, vector<int> W, ll A, ll B) {
    //min time, edge index of origin
    ll M = U.size();
    vector<array<ll,3>> adj[N];
    for (ll i=0;i<M;i++) {
        if (W[i]==0) {
            // //cout << "0U[i]="<<U[i]<<"\n";
            // //cout << "V[i]="<<V[i]<<"\n";
            adj[U[i]].push_back({V[i],A,i});
            adj[V[i]].push_back({U[i],A,i});
        } else if (W[i]==1) {
            // //cout << "1U[i]="<<U[i]<<"\n";
            // //cout << "V[i]="<<V[i]<<"\n";
            adj[U[i]].push_back({V[i],B,i});
            adj[V[i]].push_back({U[i],B,i});
        } else {
            //cout << "DIJK CALL INVALID\n"; exit(0);
        }
    }
    //exit(0);
    vector<bool> prc(N,0);
    set<array<ll,3>> q0;
    q0.insert({0,src,-1});
    vector<ll> ans(N,-1);
    vector<ll> org(N,-1);
    while (q0.size()!=0) {
        auto A0 = *q0.begin(); q0.erase(q0.begin());
        ll x = A0[1];
        ll t = A0[0];
        if (prc[x]) {
            continue;
        } else {
            prc[x]=1;
            ans[x]=t;
            org[x]=A0[2];
            for (auto A1: adj[x]) {
                q0.insert({A1[1]+t,A1[0],A1[2]});
            }
        }
    }
    return {ans,org};
}

void find_pair(int N, vector<int> U, vector<int> V, int A0, int B0) {
    //cout << "A,B="<<A0<<","<<B0<<"\n";
    ll M = U.size();
    ll A = A0; ll B = B0;
    ll val0 = ask(vector<int>(M,0));
    ll mmin = 0;
    ll mmax = M; //max # of segments that can be blocked without affecting ans
    while (mmin!=mmax) {
        ll mqry = (mmin+mmax+1)/2;
        vector<int> vq0(M,0);
        for (ll x=0;x<mqry;x++) {
            vq0[x]=1;
        }
        if (ask(vq0)==val0) {
            mmin = mqry;
        } else {
            mmax = mqry-1;
        }
    }
    ll plen = val0/A;
    //critical segment is at index mmin
    vector<int> mmc(M,0); 
    for (ll x=0;x<mmin;x++) {
        mmc[x]=1;
        //cout << "deleted segments: x="<<x<<"\n";
        //cout << "vals: U,V="<<U[x]<<","<<V[x]<<"\n";
    }
    ll c = U[mmin]; ll d = V[mmin];
    //cout << "c,d="<<c<<","<<d<<"\n";
    auto cm1 = dijk(c,N,U,V,mmc,A,B);
    auto cm0 = dijk(c,N,U,V,vector<int>(M,0),A,B);
    auto dm1 = dijk(d,N,U,V,mmc,A,B);
    auto dm0 = dijk(d,N,U,V,vector<int>(M,0),A,B);
    vector<int> mfv(M,1);
    mfv[mmin]=0;
    vector<array<ll,3>> cndS,cndT; //candidates for S/T: {+dist,x,src edge}
    for (ll x=0;x<N;x++) {
        if (cm1.first[x]==cm0.first[x] && cm0.first[x]<dm0.first[x]) {
            if (x!=c) {
                mfv[(cm1.second[x])]=0;
            }
            cndS.push_back({cm0.first[x],x,cm0.second[x]});
        }
        if (dm1.first[x]==dm0.first[x] && dm0.first[x]<cm0.first[x]) {
            if (x!=d) {
                mfv[dm1.second[x]]=0;
            }
            cndT.push_back({dm0.first[x],x,dm0.second[x]});
        }
    }
    sort(cndS.begin(),cndS.end());
    for (auto A0: cndS) {
        //cout << "cndS: "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
    }
    sort(cndT.begin(),cndT.end());
    for (auto A0: cndT) {
        //cout << "cndT: "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
    }
    ll SL = cndS.size(); ll TL = cndT.size();
    ll smin = 0; ll smax = SL-1;
    while (smin!=smax) {
        ll sqry = (smin+smax+1)/2;
        vector<int> qry = mfv;
        for (ll x=sqry;x<SL;x++) {
            qry[cndS[x][2]]=1;
        }
        if (ask(qry)==val0) {
            smax = sqry-1;
        } else {
            smin = sqry;
        }
    }
    ll tmin = 0; ll tmax = TL-1;
    while (tmin!=tmax) {
        ll tqry = (tmin+tmax+1)/2;
        vector<int> qry = mfv;
        for (ll x=tqry;x<TL;x++) {
            qry[cndT[x][2]]=1;
        }
        if (ask(qry)==val0) {
            tmax = tqry-1;
        } else {
            tmin = tqry;
        }
    }
    ll S = cndS[smin][1];
    ll T = cndT[tmin][1];
    //cout << "S="<<S<<", T="<<T<<"\n";
    answer(S,T);
}

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