Submission #932690

#	Time	Username	Problem	Language	Result	Execution time	Memory
932690		HuyQuang_re_Zero	Highway Tolls (IOI18_highway)	C++14	100 / 100	249 ms	24960 KiB

highway

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
#include "highway.h"
using namespace std;
struct Interactive
{
    ll f[maxn],n,m,i,u,v,k,s,t,A,B;
    vector <int> U,V;
    vector <II> a[maxn];
    void Init(int _n,int _m,vector <int> _U,vector <int> _V,int _A,int _B,int _s,int _t)
    {
        n=_n; m=_m; U=_U; V=_V; A=_A; B=_B; s=_s; t=_t;

        s++; t++;
        for(i=0;i<m;i++) U[i]++,V[i]++;
    }
    ll Dijkstra(vector <int> status)
    {
        for(u=1;u<=n;u++) a[u].clear();
        for(i=0;i<m;i++)
        {
            u=U[i]; v=V[i];
            if(status[i]==0) k=A; else k=B;
            a[u].push_back({ v,k }); a[v].push_back({ u,k });
        }
        for(u=1;u<=n;u++) f[u]=round(1e18);
        set <II> h;
        f[s]=0; h.insert({ 0,s });
        while(h.size()>0)
        {
            int u=h.begin()->snd; h.erase(h.begin());
            for(II adj:a[u])
            {
                int v=adj.fst,k=adj.snd;
                if(f[v]>f[u]+k)
                {
                    h.erase({ f[v],v });
                    f[v]=f[u]+k;
                    h.insert({ f[v],v });
                }
            }
        }
        return f[t];
    }
} IR;

//ll ask(vector <int> Status) { return IR.Dijkstra(Status); }
//void answer(int s,int t) { cout<<s<<" "<<t<<'\n'; }

vector <int> Deleted;
vector <II> a[maxn];
ll best_cost,best_len;
int fx[maxn],fs[maxn],i,u,v,x,node[maxn],m;
void find_pair(int n,vector <int> U,vector <int> V,int A,int B)
{
    m=U.size();
    function <ll(vector <int>)> Try_to_Delete=[&](vector <int> Try)
    {
        vector <int> status(m);
        for(int x:Deleted) status[x]=1;
        for(int x:Try) status[x]=1;
        return ask(status);
    };
    for(i=0;i<m;i++)
    {
        u=++U[i]; v=++V[i];
        a[u].push_back({ v,i }); a[v].push_back({ u,i });
    }

    /////////////////////////////////////////////////////////////////////////////////////
    //Find x
    vector <int> vec;
    best_cost=Try_to_Delete(vec);
    best_len=best_cost/A;
    int l=0,r=m-1,s,t;
    while(l<r)
    {
        int mid=(l+r)>>1;
     //   cerr<<l<<" "<<r<<" "<<mid<<'\n';
        vector <int> vec;
        for(i=0;i<=mid;i++) vec.push_back(i);
        if(Try_to_Delete(vec)>best_cost) r=mid; else l=mid+1;
    }
   // cerr<<l<<'\n';
    for(i=0;i<l;i++) Deleted.push_back(i);
    x=U[l];



    ////////////////////////////////////////////////////////////////////////////////////
    //Find s
    auto BFS=[&](int s,int f[])
    {
        for(int u=1;u<=n;u++) f[u]=round(1e9);
        queue <int> q;
        q.push(s); f[s]=0;
        while(q.size()>0)
        {
            int u=q.front(); q.pop();
         //   if(s==2) cerr<<u<<'\n';
            for(II adj:a[u])
            {
                int v=adj.fst,x=adj.snd;
                if(f[v]>f[u]+1)
                    q.push(v),f[v]=f[u]+1;
            }
        }
    };
 //   cerr<<x<<'\n';
    BFS(x,fx);
    for(i=1;i<=n;i++) node[i]=i;
    sort(node+1,node+n+1,[&](int u,int v){ return fx[u]>fx[v]; });
 //  for(i=1;i<=n;i++) cerr<<node[i]<<'\n';
    l=1; r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        vector <int> vec;
        for(i=1;i<=mid;i++)
        {
            u=node[i];
            for(II adj:a[u])
                if(fx[u]==fx[adj.fst]+1) vec.push_back(adj.snd);
        }
        if(Try_to_Delete(vec)>best_cost) r=mid; else l=mid+1;
    }
    s=node[l];


    ///////////////////////////////////////////////////////////////////////////////////////////
    //Find t
    BFS(s,fs);
 //   cerr<<fx[2]<<" "<<fx[4]<<" "<<fs[4]<<" "<<best_len<<'\n';
    vector <int> candidates;
    for(u=1;u<=n;u++)
        if(fx[s]+fx[u]==fs[u] && fs[u]==best_len)
            candidates.push_back(u);

    l=0; r=candidates.size()-1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        vector <int> vec;
        for(i=0;i<=mid;i++)
        {
            u=candidates[i];
            for(II adj:a[u])
                if(fx[u]==fx[adj.fst]+1) vec.push_back(adj.snd);
        }
        if(Try_to_Delete(vec)>best_cost) r=mid; else l=mid+1;
    }
    t=candidates[l];

    answer(s-1,t-1);
}
/*
int main()
{
    freopen("highway.inp","r",stdin);
    freopen("highway.out","w",stdout);
    int n,m,A,B,s,t,u,v;
    vector <int> U,V;
    cin>>n>>m>>A>>B>>s>>t;
    for(int i=0;i<m;i++) cin>>u>>v,U.push_back(u),V.push_back(v);
    IR.Init(n,U,V,A,B,s,t);
    find_pair(n,m,U,V,A,B);
}
*/

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:118:31: warning: unused variable 'x' [-Wunused-variable]
  118 |                 int v=adj.fst,x=adj.snd;
      |                               ^

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