Submission #1227219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227219		AlperenT_	Highway Tolls (IOI18_highway)	C++20	18 / 100	154 ms	80996 KiB

highway

#include <bits/stdc++.h> 
#include "highway.h"
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 100  , maxk = 100 + 10  , inf = 1e9+ 10 , mod = 1e9 + 9 , lg = 20 ;
int n , m ; int d[maxn]  ,mark[maxn];
vector <int> h[maxn] , h2[maxn] , G[maxn] ;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
    n = N ; 
    m = sz(U);
    int l =-1, r = n ; vector<int> www; 
    rep(i , 0 ,m-1)www.pb(0);
    ll sp = ask(www) ; 
    while(r-l > 1){
        int mid = (l+r)/2 ;
        vector <int> w; 
        rep(i , 0 ,m-1){
            if(U[i] <= mid || V[i] <= mid){
                w.pb(1);
            }else{
                w.pb(0); 
            }
        }
        ll ans = ask(w); 
        if(ans == sp){
            l = mid ;
        }else{
            r = mid ;
        }
    }
    int x  =r ;
    rep(i , 0 ,m-1){
        if(U[i] < x || V[i] < x)continue ;
        G[V[i]].pb(U[i]);
        G[U[i]].pb(V[i]); 
    }
    
    queue <int> q ;
    rep(i , 0 ,n-1)d[i] = inf; 
    d[x] = 0 ;
    q.push(x) ;
    while(sz(q)){
        int v = q.front() ;
        q.pop() ;
        for(int u : G[v]){
            if(d[u] > d[v] + 1){
                d[u] = d[v] + 1; 
                q.push(u) ; 
            }
        }
    }
    rep(i ,x , n-1){
        if(d[i]!=inf)
        h2[d[i]].pb(i) ;
    }
    rep(i , 0, m-1){
        if(U[i] < x || V[i] < x)continue ; 
        if(d[U[i]] == d[V[i]])continue ;
        if(d[U[i]]!=inf)
        h[min(d[U[i]] , d[V[i]])].pb(i);
    }
    l =-1 , r =n ;
    while(r-l > 1){
        int mid = (l+r)/2 ;
        vector <int> w; 
        rep(i , 0, m-1){
            if(U[i] < x || V[i] < x){
                w.pb(1);
                continue ; 
            }
            w.pb(0); 
        }
        rep(i , mid , n){
            for(int z : h[i]){
                w[z] = 1; 
            }
        }
        if(ask(w) == sp){
            r = mid ;
        }else{
            l = mid ;
        }
    }
    int s= r ,t ;
    l =-1 , r =sz(h2[s]);;
    rep(i , 0 ,m-1){
        if(d[U[i]] > d[V[i]])swap(U[i] , V[i]) ;
    }
    while(r-l>1){
        int mid = (l+r)/2 ;
        vector <int> w; 
        rep(i , 0, m-1){
            if(U[i] < x || V[i] < x){
                w.pb(1);
                continue ; 
            }
            w.pb(0); 
        }
        rep(i , 0 ,n-1)mark[i] = 0;
        rep(i , 0 ,mid){
            mark[h2[s][i]] = 1; 
        }
        rep(i , 0 ,m-1){
            if(U[i] < x || V[i] < x)continue ;
            if(mark[V[i]] == 1 && d[U[i]] < d[V[i]]){
                w[i] = 1;
            }
        }
        if(ask(w) == sp){
            l = mid ;
        }else{
            r = mid ;
        } 
    }
    int S = h2[s][r] ;
    q.push(S);
    rep(i , 0 ,n-1)d[i] = inf ;
    d[S] =0 ;
    while(sz(q)){
        int v = q.front() ; q.pop() ;
        for(int u : G[v]){
            if(d[u] > d[v]+1){
                d[u] = d[v]+1;
                q.push(u) ;
            }   
         }
    }
    vector<int> vec ;
    rep(i , x ,n-1){
        if(d[i] == sp/A){
            vec.pb(i) ;
        }
    }
     l =-1 , r= sz(vec);
    while(r-l >1){
        int mid = (l+r)/2 ;
        rep(i , 0 ,n-1)mark[i] =0 ; 
        rep(i , 0 ,mid){
            mark[vec[i]] = 1; 
        }
        vector <int> w; 
        rep(i , 0 ,m-1){
            if(U[i] < x || V[i] < x){
                w.pb(1);
                continue ;
            }
            if(d[U[i]] > d[V[i]])swap(V[i] , U[i]) ;
            if(mark[V[i]] == 1 && d[U[i]] < d[V[i]]){
                w.pb(1);
            }else{
                w.pb(0) ;
            }
        }
    if(ask(w) == sp){
                l = mid ;
            }else{
                r = mid ;
            }
    }
    int T = vec[r] ;
    answer(S,T) ;
}

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