Submission #982118

#	Time	Username	Problem	Language	Result	Execution time	Memory
982118		Abito	Swapping Cities (APIO20_swap)	C++17	100 / 100	227 ms	191060 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
struct edge{
    int x,y,w;
};
const int NN=7e5+5;
int n,m,p[NN],val[NN],f[NN],c,lg[NN],deg[NN],dis[NN],par[25][NN];
pair<int,int> st[25][NN];
bool spec[NN];
edge e[NN];
vector<int> adj[NN];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int getpar(int x){
    if (x==p[x]) return x;
    return p[x]=getpar(p[x]);
}
void link(int x,int y){
    x=getpar(x);y=getpar(y);
    if (x==y) return;
    p[x]=y;
    adj[y].pb(x);
    return;
}
void dfs(int x){
    st[0][++c]={dis[x],x};
    f[x]=c;
    for (auto u:adj[x]){
        par[0][u]=x;
        dis[u]=dis[x]+1;
        dfs(u);
        st[0][++c]={dis[x],x};
    }return;
}
void build(){
    for (int i=1;i<25;i++) for (int j=1;j+(1<<i)<=c+1;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    for (int i=1;i<25;i++) for (int j=1;j<=n+m;j++) par[i][j]=par[i-1][par[i-1][j]];
    return;
}
int query(int l,int r){
    if (l>r) swap(l,r);
    int i=lg[r-l+1];
    //cout<<l<<' '<<r<<' '<<i<<endl;
    return min(st[i][l],st[i][r-(1<<i)+1]).S;
}
void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
    for (int i=2;i<NN;i++) lg[i]=lg[i/2]+1;
    n=N,m=M;dis[0]=-1;
    for (int i=0;i<m;i++) e[i+1]={U[i]+1,V[i]+1,W[i]};
    sort(e+1,e+1+m,cmp);
    for (int i=1;i<=n+m;i++) p[i]=i;
    for (int i=1;i<=m;i++){
        val[i+n]=e[i].w;
        deg[e[i].x]++;
        deg[e[i].y]++;
        if (deg[e[i].x]>=3 || deg[e[i].y]>=3) spec[i+n]=1;
        int x=getpar(e[i].x),y=getpar(e[i].y);
        if (x==y){
            spec[i+n]=1;
            link(x,i+n);
        }
        else{
            link(x,i+n);
            link(y,i+n);
        }
        for (auto u:adj[i+n]) spec[i+n]|=spec[u];
    }
    dfs(n+m);
    build();
    /*for (int i=0;i<5;i++){
        for (int j=1;j+(1<<i)<=c+1;j++) cout<<st[i][j].S<<' ';
        cout<<endl;
    }*/
    return;
}

int getMinimumFuelCapacity(int x, int y) {
    if (!spec[n+m]) return -1;
    x++;y++;
    int lca=query(f[x],f[y]);
    //cout<<lca<<endl;
    if (spec[lca]) return val[lca];
    for (int i=24;i>=0;i--){
        if (par[i][lca]==0) continue;
        if (spec[par[i][lca]]) continue;
        lca=par[i][lca];
    }
    return val[par[0][lca]];
}

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