Submission #714433

#	Time	Username	Problem	Language	Result	Execution time	Memory
714433		victor_gao	Highway Tolls (IOI18_highway)	C++17	6 / 100	102 ms	18004 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii>g[90015];
vector<ll>all[90015][2],root[2];
vector<int>qry;
ll n,m,mx[2],mn,a,b,d,fa[90015],dep[90015];
ll S=74466,T=67848;
void bfs(int r1,int r2){
    for (int i=0;i<=n;i++){
        fa[i]=0; dep[i]=0; mx[0]=1; mx[1]=1;
        all[i][0].clear();
        all[i][1].clear();
    }
    queue<pii>q; 
    q.push({r1,0}); q.push({r2,1});
    dep[r1]=1; dep[r2]=1;
    fa[r1]=-1; fa[r2]=-1;
    while (!q.empty()){
        auto [p,rt]=q.front(); q.pop();
        root[rt].push_back(p);
        all[dep[p]][rt].push_back(p);
        mx[rt]=max(mx[rt],dep[p]);
        for (auto [i,idx]:g[p]){
            if (!dep[i]){
                dep[i]=dep[p]+1; fa[i]=idx;
                q.push({i,rt});
            }
        }
    }
}
int find(int f,int p){
    if (p==1) return all[p][f][0];
    for (auto i=2;i<=n;i++){
        for (auto j:all[i][f^1])
            qry[fa[j]]=1;
    }
    for (int i=2;i<=n;i++){
        if (p!=i){
            for (auto j:all[i][f])
                qry[fa[j]]=1;
        }
    }
    ll l=0,r=all[p][f].size();
    /*
    for (auto i:all[p][f]){
        if (S==i||T==i)
            cout<<"OK\n";
    }
    */
    while (l<r){
        int mid=(l+r)>>1;
        for (int j=l;j<=mid;j++)
            qry[fa[all[p][f][j]]]=1;
        ll dis=ask(qry);
        for (int j=l;j<=mid;j++)
            qry[fa[all[p][f][j]]]=0;
        if (dis==mn+d*(b-a)) r=mid;
        else l=mid+1;
    }
    for (auto i=2;i<=n;i++){
        for (auto j:all[i][f^1])
            qry[fa[j]]=0;
    }
    for (int i=2;i<=n;i++){
        if (p!=i){
            for (auto j:all[i][f])
                qry[fa[j]]=0;
        }
    }
  //  cout<<"find "<<l<<" "<<all[p][f].size()<<' '<<all[p][f][l]<<'\n';
    return all[p][f][l];
}
void solve1(int u,int v,int _i){
    fill(qry.begin(),qry.end(),1);
    qry[_i]=0;
    bfs(u,v);
    for (int i=0;i<=n;i++){
        for (auto j:all[i][0]){
            if (fa[j]!=-1)
                qry[fa[j]]=0;
        }
    }
    ll ldep=ask(qry);
    /*
    cout<<"query : ";
    for (int i=0;i<m;i++)
        cout<<qry[i];
    cout<<" : "<<ldep<<'\n';
    */
    for (int i=0;i<=n;i++){
        for (auto j:all[i][0]){
            if (fa[j]!=-1) qry[fa[j]]=1;
        }
    }
    /*
    cout<<"group1 : ";
    for (int i=0;i<=n;i++)
        for (auto j:all[i][0])
            cout<<j<<" ";
    cout<<"\ngroup2 : ";
    for (int i=0;i<=n;i++)
        for (auto j:all[i][1])
            cout<<j<<" ";
    cout<<'\n';
    */
    ldep=d-((ldep-mn)/(b-a)); qry[_i]=1;
 //   cout<<"dep : "<<ldep<<" "<<d<<'\n';
    int s=find(0,ldep);
    int t=find(1,d-ldep+1);
 //   cout<<"answer "<<s<<" "<<t<<'\n';
    answer(s,t);
    return;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n=N; m=U.size(); a=A; b=B;
    for (int i=0;i<m;i++){
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }
    qry.resize(m,0);
    mn=ask(qry); d=mn/A;
    int l=0,r=m-1,u,v;
    while (l<r){
        int mid=(l+r)>>1;
        for (int i=0;i<=mid;i++)
            qry[i]=1;
        ll now=ask(qry);
        /*
        cout<<"query : ";
        for (int i=0;i<m;i++)
            cout<<qry[i];
        cout<<" -> "<<now<<'\n';
        */
        for (int i=0;i<=mid;i++)
            qry[i]=0;
        if (now!=mn) r=mid;
        else l=mid+1;
    }
    u=U[l]; v=V[l];
 //   cout<<"solve "<<u<<" "<<v<<'\n';
    solve1(u,v,l);
}
/*
./rand
./highway
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/

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