Submission #525119

#	Time	Username	Problem	Language	Result	Execution time	Memory
525119		leaked	Highway Tolls (IOI18_highway)	C++14	69 / 100	239 ms	14048 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>


#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=1e5+1;
vec<pii> g[N];
int p[N];
void find_pair(int n,vec<int> _v,vec<int> _u,int a,int b){
    int m=sz(_u);
    int l=0,r=m-1;
    vec<int>kek(m,1);
    ll dst=ask(kek);
    ll lst=N;
//    cout<<dst<<endl;
    auto check=[&](vec<int> ids){
        vec<int> w(m,1);
        for(auto &z : ids) w[z]=0;
        return ask(w);
    };
    map<int,ll>vl;
    while(l!=r){
        int tm=(l+r)>>1;
        vec<int>ids;
        for(int j=0;j<=tm;j++)
            ids.pb(j);
        lst=check(ids);
        vl[tm]=lst;
//        cout<<dst<<' '<<check(ids)<<endl;
        if(lst<dst)
            r=tm;
        else
            l=tm+1;
    }
    for(int i=0;i<m;i++){
        g[_v[i]].pb({_u[i],i});
        g[_u[i]].pb({_v[i],i});
    }
    int titi=l;
    lst=vl[l];
    assert(lst!=0);
//    cout<<"ALO "<<a<<' '<<b<<' '<<lst<<' '<<lst+b+a<<' '<<(lst-a)/b*a +a<<endl;
    int v=_v[l],u=_u[l];
    queue<int>q;
    vec<int>d1(n,2e9),d2(n,2e9);
    vec<int>p1(n),p2(n);
    p1[v]=l;d1[v]=0;
    q.push(v);
    while(!q.empty()){
        int ct=q.front();q.pop();
        for(auto &z : g[ct]){
            if(d1[z.f]>d1[ct]+1){
                d1[z.f]=d1[ct]+1;
                p1[z.f]=z.s;
                q.push(z.f);
            }
        }
    }
    p2[u]=l;d2[u]=0;
    q.push(u);
    while(!q.empty()){
        int ct=q.front();q.pop();
        for(auto &z : g[ct]){
            if(d2[z.f]>d2[ct]+1){
                d2[z.f]=d2[ct]+1;
                p2[z.f]=z.s;
//                cout<<"P@ "<<z.f<<' '<<z.s<<endl;
                q.push(z.f);
            }
        }
    }

    ///find s
    vec<int>p;
    vec<int> toadd,vc;
//    for(int i=0;i<m;i++) vc.pb(i);
    for(int i=0;i<n;i++){
        if(d1[i]<d2[i]) p.pb(i);
        else if(d2[i]<d1[i]) toadd.pb(p2[i]);
        vc.pb(p1[i]);
        vc.pb(p2[i]);
    }
//    cout<<d1[86771]+d2[33394]+1<<endl;
//    cout<<d1[33394]+d2[86771]+1<<endl;
//    cout<<"ALO "<<check(vc)<<endl;
    sort(all(p),[&](int i,int j){return d1[i]<d1[j];});
    l=0,r=sz(p)-1;
    ll cnt=(lst-a)/b +1;
    ll need=check(vc);
    while(l!=r){
        int tm=(l+r)>>1;
        vec<int>ids;
        for(int j=0;j<=tm;j++) ids.pb(p1[p[j]]);
        for(auto &j : toadd) ids.pb(j);
        if(check(ids)!=need) l=tm+1;
        else r=tm;
    }
    toadd.clear();
//    --l;
    int s=p[l];
    p.clear();
    for(int i=0;i<n;i++){
//        cout<<d1[i]<<' '<<d2[i]<<endl;
        if(d2[i]<d1[i]) p.pb(i);
        else if(d1[i]<d2[i]) toadd.pb(p1[i]);
    }
    sort(all(p),[&](int i,int j){return d2[i]<d2[j];});
//    for(auto &z : p)
//        cout<<z<<' '<<d2[z]<<endl;
//    cout<<"CHS "<<check(toadd)<<' '<<need<<endl;
    l=0,r=sz(p)-1;
    while(l!=r){
        int tm=(l+r)>>1;
        vec<int>ids;
        for(int j=0;j<=tm;j++) ids.pb(p2[p[j]]);
//        cout<<"SZ "<<sz(toadd)<<endl;
        for(auto &j : toadd) ids.pb(j);
//        cout<<"AUE "<<tm<<' '<<check(ids)<<' '<<need<<' '<<tm<<endl;
        if(check(ids)!=need) l=tm+1;
        else r=tm;
    }
    int t=p[l];
//    assert(check({p2[16565]}));
//    cout<<"V "<<v<<' '<<u<<endl;
//    cout<<"AS "<<s<<' '<<t<<' '<<d2[16565]<<' '<<d1[16565]<<endl;
    answer(s,t);
}
/*



*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:52:9: warning: unused variable 'titi' [-Wunused-variable]
   52 |     int titi=l;
      |         ^~~~
highway.cpp:101:8: warning: unused variable 'cnt' [-Wunused-variable]
  101 |     ll cnt=(lst-a)/b +1;
      |        ^~~

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