Submission #952405

#	Time	Username	Problem	Language	Result	Execution time	Memory
952405		hyforces	Swapping Cities (APIO20_swap)	C++14	13 / 100	387 ms	48524 KiB

swap

#include<bits/stdc++.h>
#include"swap.h"
using namespace std;
#define N 100100
#define J 18
#define inf 0x3f3f3f3f
vector<pair<int,int>>adj[N];
int parent[N],fae[N];
pair<int,int>jump[N][J];
int tin[N],tout[N],t;
void dfs(int u,int fa){
    tin[u]=++t;
    jump[u][0]={parent[u],fae[u]};
    for(int a=1;a<J;++a){
        jump[u][a]={jump[jump[u][a-1].first][a-1].first,max({jump[u][a-1].second,jump[jump[u][a-1].first][a-1].second})};
    }
    for(auto a:adj[u]){
        if(a.first==fa)continue;
        fae[a.first]=a.second;
        parent[a.first]=u;
        dfs(a.first,u);
    }
    tout[u]=t;
}
bool isanc(int u,int v){
    return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
int get(int u,int v){
    int ret=0;
    for(int a=J-1;a>=0;--a){
        if(!isanc(jump[u][a].first,v)){
            ret=max(ret,jump[u][a].second);
            u=jump[u][a].first;
        }
    }
    for(int a=J-1;a>=0;--a){
        if(!isanc(jump[v][a].first,u)){
            ret=max(ret,jump[v][a].second);
            v=jump[v][a].first;
        }
    }
    if(u==v)return ret;
    if(parent[u]==v)return max(ret,fae[u]);
    if(parent[v]==u)return max(ret,fae[v]);
    return max({ret,fae[u],fae[v]});
}

int deg[N],kt[N];
int ktv=0;

int getMinimumFuelCapacity(int u,int v){
    int ret=max(get(u,v),min(kt[u],kt[v]));
    return ret==inf?-1:max(ret,0);
}

struct DSU{
    bool mark[N];
    int fa[N];
    vector<int>buk[N];
    void activate(int u){
        if(mark[u])return;
        mark[u]=true;
        for(auto a:buk[u])kt[a]=ktv;
    }
    int root(int u){return fa[u]==u?u:fa[u]=root(fa[u]);}
    bool merge(int u,int v){
        u=root(u),v=root(v);
        if(u==v){
            activate(u);
            return false;
        }
        if(mark[u])activate(v);
        if(mark[v])activate(u);
        mark[u]|=mark[v];
        if(buk[u].size()<buk[v].size())buk[u].swap(buk[v]);
        for(auto a:buk[v])buk[u].push_back(a);
        buk[v].clear();
        fa[v]=u;
        return true;
    }
    void init(){
        for(int a=0;a<N;++a){
            fa[a]=a;
            buk[a].push_back(a);
        }
    }
}calc;

void init(int n,int m,vector<int>U,vector<int>V,vector<int>W){
    memset(kt,0x3f,sizeof(kt));
    calc.init();
    vector<int>ord;
    for(int a=0;a<m;++a)ord.push_back(a);
    sort(ord.begin(),ord.end(),[&](const int&x,const int&y)->bool{return W[x]<W[y];});
    for(int i=0;i<m;++i){int a=ord[i];
        ktv=W[a];
        if((++deg[U[a]])>=3)calc.activate(U[a]);
        if((++deg[V[a]])>=3)calc.activate(V[a]);
        if(calc.merge(U[a],V[a])){
            adj[U[a]].push_back({V[a],W[a]});
            adj[V[a]].push_back({U[a],W[a]});
        }
    }
    dfs(0,0);
}

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