Submission #732553

#	Time	Username	Problem	Language	Result	Execution time	Memory
732553		bin9638	Swapping Cities (APIO20_swap)	C++17	13 / 100	781 ms	63592 KiB

swap

#include <bits/stdc++.h>

#ifndef SKY
#include "swap.h"
#endif // SKY

using namespace std;

#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

const int root=2;

vector<ii>g[N];
vector<int>f[N];
vector<ii>vec[N];
int sz[N],n,m,head[N],dp[N],times,LOG,chain,in[N],pos[N],picked[N],MV[N];
ii cha[N][21],cnt[N];

struct IT_LAZY
{
    int ST[N*4]={};

    void init()
    {
        for(int i=1;i<=n*4;i++)
            ST[i]=2e9;
    }

    void update(int id,int l,int r,int u,int v,int val)
    {
        if(l>v||r<u)
            return;
        if(l>=u&&r<=v)
        {
            ST[id]=min(ST[id],val);
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,u,v,val);
        update(id*2+1,mid+1,r,u,v,val);
    }

    int get(int id,int l,int r,int i)
    {
        if(l>i||r<i)
            return 2e9;
        if(l==r)
            return ST[id];
        int res=ST[id];
        int mid=(l+r)/2;
        res=min(res,get(id*2,l,mid,i));
        res=min(res,get(id*2+1,mid+1,r,i));
        return res;
    }

    void hld_update(int r,int u,int cost)
    {
        while(in[u]!=in[r])
        {
            update(1,1,n,pos[head[in[u]]],pos[u],cost);
            u=cha[head[in[u]]][0].sc;
        }
        if(r==u)
            return;
        update(1,1,n,pos[MV[u]],pos[u],cost);
    }
}IT_LAZY;

struct IT
{
    int ST[N*4]={};

    void init()
    {
        for(int i=1;i<=n*4;i++)
            ST[i]=2e9;
    }

    void update(int id,int l,int r,int i,int val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id]=min(ST[id*2],ST[id*2+1]);
    }

    int get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return 2e9;
        if(l>=u&&r<=v)
            return ST[id];
        int mid=(l+r)/2;
        return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}IT;

struct DSU
{
    int lab[N];

    void init()
    {
        memset(lab,-1,sizeof(lab));
    }

    int root(int u)
    {
        if(lab[u]<0)
            return u;
        return(lab[u]=root(lab[u]));
    }

    bool update(int u,int v)
    {
        if((u=root(u))==(v=root(v)))
            return 0;
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
        return 1;
    }
}DSU;

struct canh
{
    int u,v,w;

    bool operator<(const canh&A)const
    {
        return w<A.w;
    }
};
vector<canh>edge;

int get_min(int u,int A,int B)
{
    if(f[u].size()<3)
        return 2e9;
    if(A>B)
        swap(A,B);
    if(f[u][0]!=A)
        return f[u][0];
    if(f[u][1]!=B)
        return f[u][1];
    return f[u][2];
}

void DFS(int u,int p)
{
    cnt[u].fs=++times;
    sz[u]=1;
    for(auto v:g[u])
        if(v.sc!=p)
        {
            cha[v.sc][0]={v.fs,u};
            DFS(v.sc,u);
            sz[u]+=sz[v.sc];
        }
    cnt[u].sc=times;
}

void hld(int u,int p)
{
    in[u]=chain;
    pos[u]=++times;
    if(head[chain]==0)
        head[chain]=u;
    for(auto v:g[u])
        if(v.sc!=p&&(MV[u]==0||sz[v.sc]>sz[MV[u]]))
            MV[u]=v.sc;
    if(MV[u]==0)
        return;
    hld(MV[u],u);
    for(auto v:g[u])
        if(v.sc!=p&&v.sc!=MV[u])
        {
            chain++;
            hld(v.sc,u);
        }
}

bool tren(int u,int v)
{
    return(cnt[u].fs<=cnt[v].fs&&cnt[u].sc>=cnt[v].sc);
}

int lca(int u,int v)
{
    if(tren(u,v))
        return u;
    if(tren(v,u))
        return v;
    for(int k=LOG;k>=0;k--)
        if(cha[u][k].sc!=0&&!tren(cha[u][k].sc,v))
            u=cha[u][k].sc;
    return cha[u][0].sc;
}

int con_duoi(int r,int u)
{
    for(int k=LOG;k>=0;k--)
        if(cha[u][k].sc!=0&&!tren(cha[u][k].sc,r))
            u=cha[u][k].sc;
    return u;
}

int get_max(int r,int u)
{
    if(r==u)
        return 0;
    int res=0;
    for(int k=LOG;k>=0;k--)
        if(cha[u][k].sc!=0&&!tren(cha[u][k].sc,r))
        {
            res=max(res,cha[u][k].fs);
            u=cha[u][k].sc;
        }
    return max(res,cha[u][0].fs);
}

int get_2_con(int u,int A)
{
    if(f[u].size()<3)
        return 2e9;
    if(f[u][0]==A)
        return max(f[u][1],f[u][2]);
    if(f[u][1]==A)
        return max(f[u][0],f[u][2]);
    return max(f[u][0],f[u][1]);
}

void build(int u,int p)
{
    if(u!=root)
        dp[u]=get_2_con(u,cha[u][0].fs);
    for(auto v:g[u])
        if(v.sc!=p)
        {
            build(v.sc,u);
            dp[u]=min(dp[u],max(v.fs,dp[v.sc]));
        }
}

void nguoc(int u,int p,int val)
{
    for(auto v:g[u])
        if(v.sc!=p)
            vec[u].pb({max(v.fs,dp[v.sc]),v.sc});
    sort(vec[u].begin(),vec[u].end());
    for(auto v:g[u])
        if(v.sc!=p)
        {
            if(v.sc==vec[u][0].sc)
            {
                nguoc(v.sc,u, max(v.fs,min((vec[u].size()<2 ? (int)2e9 : vec[u][1].fs),val)));
            }else
            {
                nguoc(v.sc,u,max(v.fs,min(vec[u][0].fs,val)));
            }
        }
    vec[u].clear();
    for(auto v:g[u])
        if(v.sc!=p&&dp[v.sc]<=1e9)
            vec[u].pb({max(v.fs,dp[v.sc]),v.sc});
    if(val<=1e9)
        vec[u].pb({val,p});
    sort(vec[u].begin(),vec[u].end());
}

void init(int NNN, int MMM,vector<int> UUU,vector<int> VVV, vector<int> WWW)
{
    n=NNN;
    m=MMM;
  //  assert(m==n-1);
    for(int i=0;i<m;i++)
    {
        UUU[i]++;
        VVV[i]++;
        edge.pb({UUU[i],VVV[i],WWW[i]});
        f[UUU[i]].pb(WWW[i]);
        f[VVV[i]].pb(WWW[i]);
    }
    sort(edge.begin(),edge.end());
    DSU.init();
    for(int i=0;i<m;i++)
        if(DSU.update(edge[i].u,edge[i].v))
        {
          //  cout<<edge[i].u-1<<" "<<edge[i].v-1<<endl;
            picked[i]=1;
            g[edge[i].u].pb({edge[i].w,edge[i].v});
            g[edge[i].v].pb({edge[i].w,edge[i].u});
        }
    for(int i=1;i<=n;i++)
        sort(f[i].begin(),f[i].end());
   DFS(root,0);
   times=0;
   hld(root,0);
    LOG=log2(n);
    for(int k=1;k<=LOG;k++)
        for(int i=1;i<=n;i++)
          cha[i][k]={max(cha[cha[i][k-1].sc][k-1].fs,cha[i][k-1].fs),cha[cha[i][k-1].sc][k-1].sc};
    IT.init();
    for(int i=1;i<=n;i++)
        if(i!=root&&cha[i][0].sc!=root)
            IT.update(1,1,n,pos[i],get_min(cha[i][0].sc,cha[i][0].fs,cha[cha[i][0].sc][0].fs));
    IT_LAZY.init();
    for(int i=0;i<m;i++)
        if(picked[i]==0)
        {
            int u=edge[i].u,v=edge[i].v,r=lca(u,v),cost=max(edge[i].w,max(get_max(r,u),get_max(r,v)));
            IT_LAZY.hld_update(r,u,cost);
            IT_LAZY.hld_update(r,v,cost);
        }
    memset(dp,0x3f3f,sizeof(dp));
    build(root,0);
    nguoc(root,0,2e9);
   // exit(0);
}

int get(int r,int u)
{
    int res=2e9;
    while(in[u]!=in[r])
    {
        res=min(res,IT.get(1,1,n,pos[head[in[u]]],pos[u]));
        u=cha[head[in[u]]][0].sc;
    }
    if(u==r)
        return res;
    return min(res,IT.get(1,1,n,pos[MV[r]],pos[u]));
}

int get_cay_vl(int u,int c)
{
    if(vec[u].empty())
        return 2e9;
    if(vec[u][0].sc==c)
    {
        if(vec[u].size()<2)
            return 2e9;
        return vec[u][1].fs;
    }
    return vec[u][0].fs;
}

int getMinimumFuelCapacity(int u, int v)
{
    u++;
    v++;
    int r=lca(u,v),res=2e9;///max(get_max(r,u),get_max(r,v));
    if(r==u)
        swap(u,v);
     //  cout<<u-1<<" "<<v-1<<" "<<r-1<<" "<<con_duoi(r,u)-1<<endl;
    if(u!=r)
        res=min(res,get(con_duoi(r,u),u));
    if(v!=r)
        res=min(res,get(con_duoi(r,v),v));
   // assert(v==1||u==1);
    if(r==v)
    {
        res=min(res,get_2_con(r,cha[con_duoi(r,u)][0].fs));
        res=min(res,get_2_con(u,cha[u][0].fs));
        res=min(res,get_cay_vl(r,con_duoi(r,u)));
        res=min(res,get_cay_vl(u,cha[u][0].sc));
    }else
    {
        res=min(res,get_2_con(u,cha[u][0].fs));
        res=min(res,get_2_con(v,cha[v][0].fs));
        res=min(res,get_min(r,cha[con_duoi(r,u)][0].fs,cha[con_duoi(r,v)][0].fs));
       res=min(res,get_cay_vl(u,cha[u][0].sc));
       res=min(res,get_cay_vl(v,cha[v][0].sc));
    }
    res=min(res,IT_LAZY.get(1,1,n,pos[u]));
   // cout<<res<<endl;
    res=max(res,max(get_max(r,u),get_max(r,v)));
    if(res<=1e9)
        return res;
            else return -1;
}


#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<int>U(m),V(m),W(m);
    for(int i=0;i<m;i++)
        cin>>U[i];
    for(int i=0;i<m;i++)
        cin>>V[i];
    for(int i=0;i<m;i++)
        cin>>W[i];
    init(n,m,U,V,W);
    int q;
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        cout<<getMinimumFuelCapacity(u,v)<<endl;
    }
    return 0;
}
#endif

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27