Submission #1244889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244889		jeroenodb	Highway Tolls (IOI18_highway)	C++20	51 / 100	93 ms	9752 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int m = U.size();
    int n = N;
    vi w(m);
    ll dist = ask(w)/A;
    vvi adj(n);
    for(int i=0;i<m;++i) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
    int lo = 1, hi = m;
    while(lo<hi) {
        int mid = (lo+hi)/2;
        w.assign(m,1);
        fill(w.begin(),w.begin()+mid,0);
        if(ask(w)==dist*ll(A)) {
            // great, some shortest path!
            hi = mid;
        } else lo = mid+1;
    }
    auto bfs = [&](int s) {
        vi d(n,oo);
        d[s]=0;
        vi q = {s};
        for(int i=0;i<n;++i) {
            int at = q[i];
            for(int to : adj[at]) if(d[to]==oo) {
                d[to]=d[at]+1;
                q.push_back(to);
            }
        }
        return d;
    };
    const int M = lo;

    lo--;
    auto du = bfs(U[lo]);
    auto dv = bfs(V[lo]);
    vi su,sv;
    for(int i=0;i<n;++i) {
        if(du[i]==dv[i]+1 and dv[i]<dist) {
            sv.push_back(i);
        } else if(du[i]+1==dv[i] and du[i]<dist) {
            su.push_back(i);
        }
    }
    int lu,lv;
    {
        vector<bool> good(n);
        for(int i : su) if(du[i]<dist) good[i]=1;
        w.assign(m,1);
        for(int i=0;i<M;++i) {
            w[i] = !good[U[i]] or !good[V[i]];
            
        }
        ll have = ask(w);
        // A*lu + B*(lv+1) == have
        // lu+(lv+1)==dist
        // (lv+1) == dist-lu
        // A*lu + B*(dist-lu) == have
        // (A-B)*lu = have-B*dist
        lu = (have-ll(B)*dist)/(A-B);
        lv = dist-1-lu;
    }
    auto solve = [&](vi special, vi d, int l) {
        special.erase(partition(all(special),[&](int i) {return d[i]==l;}),special.end());       
        int k = special.size();        
        int lo = 1, hi = k;
        while(lo<hi) {
            fill(all(w),1);
            vector<bool> want(n);

            int mid = (lo+hi)/2;
            for(int i=0;i<mid;++i) want[special[i]]=1;
            for(int i=0;i<=M;++i) {
                int u = U[i], v = V[i];
                if(d[u]>d[v]) swap(u,v);
                if(want[v] and d[u]+1==d[v]) {
                    want[v]=0;
                    w[i]=0;
                }
            }
            ll my = ask(w);
            if(my == (dist-1)*ll(B) + A) {
                hi = mid;
            } else lo = mid+1;

        }
        return special[lo-1];
    };
    int s = solve(su,du,lu);
    int t = solve(sv,dv,lv);
    answer(s,t);


}

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