Submission #319483

#	Time	Username	Problem	Language	Result	Execution time	Memory
319483		knon0501	Swapping Cities (APIO20_swap)	C++14	6 / 100	413 ms	41676 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MX=3e5+5;
int sz[MX];
int p[MX][20];
int nn,n;
int pr[MX];
int w[MX];
int dth[MX];
int b[MX];
int E[MX];
int c[MX];
int deg[MX];
int mdeg[MX];
vector<int> a[MX];

struct A{
    int u,v,w;
    bool operator <(const A&r)const{
        return w<r.w;
    }
}e[MX];

int lca(int v,int u){
    int i,j;
    if(dth[v]>dth[u])swap(u,v);
    for(i=19 ; i>=0 ; i--)if(dth[u]-dth[v]>=(1<<i))u=p[u][i];
    if(u==v)return v;
    for(i=19 ; i>=0 ; i--){
        if(p[u][i]!=p[v][i]){
            u=p[u][i];
            v=p[v][i];
        }
    }
    return p[v][0];
}
int f(int k){
    return k==pr[k] ? k:pr[k]=f(pr[k]);
}
void Union(A k){
    deg[k.u]++;
    deg[k.v]++;

    int x=f(k.u);
    int y=f(k.v);

    if(x==y){
        E[x]++;
        mdeg[x]=max({mdeg[x],deg[k.u],deg[k.v]});
        if(b[x]==-1)
            b[x]=k.w;
        return;
    }
    pr[x]=nn;
    pr[y]=nn;
    mdeg[nn]=max({mdeg[x],mdeg[y],deg[k.u],deg[k.v]});
    sz[nn]=sz[x]+sz[y];
    E[nn]=E[x]+E[y]+1;
    w[nn]=k.w;
    a[nn].push_back(x);
    a[nn].push_back(y);
    p[x][0]=nn;
    p[y][0]=nn;
    if(E[nn]>=sz[nn] && b[nn]==-1 ){
        b[nn]=k.w;
    }
    if(mdeg[nn]>=3 && b[nn]==-1)
        b[nn]=k.w;
    nn++;
}
void dfs(int v,int pp){
    if(E[v]>=sz[v] || mdeg[nn]>=3)c[v]=v;
    else if(p[v][0]>=0)c[v]=c[p[v][0]];
    else c[v]=-1;
    for(auto u:a[v]){
        if(u==pp)continue;
        dth[u]=dth[v]+1;
        dfs(u,v);
    }
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    nn=n=N;
    int i,j;
    for(i=0 ; i<M; i++){
        e[i]={U[i],V[i],W[i]};
    }
    sort(e,e+M);
    for(i=0 ;i<N ; i++)sz[i]=1;
    for(i=0 ; i<N+M ; i++)pr[i]=i,p[i][0]=-1,b[i]=-1;
    for(i=0 ; i<M ; i++){
        Union(e[i]);

    }
    for(i=0 ; i<nn ; i++)
        if(p[i][0]==-1)
            dfs(i,-1);
    for(i=1 ; i<20 ; i++){
        for(j=0 ; j<nn ; j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }

}

int getMinimumFuelCapacity(int X, int Y) {
    int k=lca(X,Y);
    if(c[k]==-1)return -1;
    return b[c[k]];
}

Compilation message (stderr)

swap.cpp: In function 'int lca(int, int)':
swap.cpp:27:11: warning: unused variable 'j' [-Wunused-variable]
   27 |     int i,j;
      |           ^

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