Submission #928402

#	Time	Username	Problem	Language	Result	Execution time	Memory
928402		User0069	Swapping Cities (APIO20_swap)	C++17	0 / 100	19 ms	59996 KiB

swap

#include<bits/stdc++.h>
//#include"swap.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e6+1;
const int INF=1e9+7;
const int mod=1e9+7;
int n,m,d[maxn],cnt[maxn],par[maxn],h[maxn],up[maxn][20],f[maxn][20],g[maxn][20],laz[maxn][20];
struct edge
{
    int u,v,w,used;
}e[maxn];
vector<int> adj[maxn];
bool operator <(edge a,edge b)
{
    return a.w<b.w;
}
int fp(int x)
{
    if(par[x]<0) return x;
    return par[x]=fp(par[x]);
}
void uni(int a,int b)
{
    a=fp(a);
    b=fp(b);
    if(a==b) return;
    if(par[a]>par[b]) swap(a,b);
    par[a]+=par[b];
    par[b]=a;
}
void dfs(int x,int par)
{
    h[x]=h[par]+1;
    up[x][0]=par;
    for(int i:adj[x])
    {
        int y=e[i].u+e[i].v-x;
        if(y==par) continue;
        f[y][0]=e[i].w;
        dfs(y,x);
    }
}
struct ele
{
    int des,dis;
};
bool operator <(ele a,ele b)
{
    return a.dis>b.dis;
}
void dijkstra()
{
    priority_queue<ele> pq;
    for(int i=1;i<=n;i++)
    {
        pq.push({i,d[i]});
        cnt[i]=0;
    }
    while(!pq.empty())
    {
        int des=pq.top().des;
        int dis=pq.top().dis;
        pq.pop();
        if(cnt[des]) continue;
        cnt[des]=1;
        d[des]=dis;
        for(int i:adj[des])
        {
            int des1=e[i].u+e[i].v-des;
            pq.push({des1,max(dis,e[i].w)});
        }
    }
    for(int i=1;i<=n;i++)
    {
        g[i][0]=d[i];
    }
}
void update(int x,int y,int w)
{
    if(h[x]!=h[y])
    {
        if(h[x]<h[y]) swap(x,y);
        int dif=h[x]-h[y];
        for(int i=0;i<20;i++)
        {
            if(dif&(1<<i))
            {
                laz[x][i]=min(laz[x][i],w);
                x=up[x][i];
            }
        }
    }
    if(x!=y)
    {
        int lg=__lg(h[x]);
        for(int i=lg;i>=0;i--)
        {
            if(up[x][i]!=up[y][i])
            {
                laz[x][i]=min(laz[x][i],w);
                laz[y][i]=min(laz[y][i],w);
                x=up[x][i];
                y=up[y][i];
            }
        }
        laz[x][0]=min(laz[x][0],w);
        laz[y][0]=min(laz[y][0],w);
        x=up[x][0];
    }
    laz[x][0]=min(laz[x][0],w);
}
void init(int _n,int _m,vector<int> _u,vector<int> _v,vector<int> _w)
{
    n=_n;
    m=_m;
    for(int i=0;i<m;i++)
    {
        e[i+1].u=++_u[i];
        e[i+1].v=++_v[i];
        e[i+1].w=_w[i];
        e[i+1].used=0;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        par[i]=-1;
    }
    for(int i=1;i<=m;i++)
    {
        if(++cnt[e[i].u]==3) d[e[i].u]=e[i].w;
        if(++cnt[e[i].v]==3) d[e[i].v]=e[i].w;
        if(fp(e[i].u)!=fp(e[i].v))
        {
            uni(e[i].u,e[i].v);
            adj[e[i].u].push_back(i);
            adj[e[i].v].push_back(i);
            e[i].used=1;
        }
    }
    dfs(1,0);
    dijkstra();
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<20;j++)
        {
            laz[i][j]=INF;
        }
    }
    for(int j=1;j<20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            up[i][j]=up[up[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(e[i].used==0)
        {
           update(e[i].u,e[i].v,e[i].w);
        }
    }
    for(int j=1;j<20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            f[i][j]=max(f[i][j-1],f[up[i][j-1]][j-1]);
            g[i][j]=min(g[i][j-1],g[up[i][j-1]][j-1]);
        }
    }
    for(int j=19;j;j--)
    {
        for(int i=1;i<=n;i++)
        {
            laz[i][j-1]=min(laz[i][j-1],laz[i][j]);
            laz[up[i][j-1]][j-1]=min(laz[up[i][j-1]][j-1],laz[i][j]);
        }
    }
}
int getMinimumFuelCapacity(int x,int y)
{
    int w1=0,w2=INF;
    if(h[x]!=h[y])
    {
        if(h[x]<h[y]) swap(x,y);
        int dif=h[x]-h[y];
        for(int i=0;i<20;i++)
        {
            if(dif&(1<<i))
            {
                w1=max(w1,f[x][i]);
                w2=min(w2,g[x][i]);
                x=up[x][i];
            }
        }
    }
    if(x!=y)
    {
        int lg=__lg(h[x]);
        for(int i=lg;i>=0;i--)
        {
            if(up[x][i]!=up[y][i])
            {
                w1=max(w1,f[x][i]);
                w2=min(w2,g[x][i]);
                w1=max(w1,f[y][i]);
                w2=min(w2,g[y][i]);
                x=up[x][i];
                y=up[y][i];
            }
        }
        w1=max(w1,f[x][0]);
        w1=max(w1,f[y][0]);
        w2=min(w2,g[x][0]);
        w2=min(w2,g[y][0]);
        x=up[x][0];
    }
    w2=min(w2,g[x][0]);
    int ans=max(w1,min(w2,laz[x][0]));
    if(ans==INF) return -1;
    else return ans;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    int n,m,q;
//    vector<int> v1,v2,v3;
//    cin>>n>>m>>q;
//    for(int i=1; i<=m; i++)
//    {
//        int u,v,w;
//        cin>>u>>v>>w;
//        v1.push_back(u);
//        v2.push_back(v);
//        v3.push_back(w);
//    }
//    init(n,m,v1,v2,v3);
//    while(q--)
//    {
//        int u,v;
//        cin>>u>>v;
//        cout<<getMinimumFuelCapacity(++u,++v)<<"\n";
//    }
//}

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