Submission #717532

#	Time	Username	Problem	Language	Result	Execution time	Memory
717532		alvingogo	Swapping Cities (APIO20_swap)	C++14	100 / 100	404 ms	43376 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct TR{
    vector<vector<int> > e;
    vector<array<int,20> > as;
    vector<int> tag;
    vector<int> dep;
    vector<int> val;
    int sz=0;
    void init(int x){
        e.resize(x);
        as.resize(x);
        dep.resize(x,-1);
        val.resize(x,2e9);
        sz=x;
    }
    void add(int cnt){
        //cout << sz << " " << cnt << "\n";
        e.push_back(vector<int>());
        as.push_back(array<int,20>());
        dep.push_back(-1);
        val.push_back(cnt);
        sz++;
    }
    void eg(int a,int b){
        //cout << a << "e" << b << '\n';
        e[a].push_back(b);
    }
    void dfs(int r,int f){
        as[r][0]=f;
        val[r]=min(val[r],val[f]);
        dep[r]=dep[f]+1;
        for(int i=1;i<20;i++){
            as[r][i]=as[as[r][i-1]][i-1];
        }
        for(auto h:e[r]){
            dfs(h,r);
        }
    }
    int lca(int a,int b){
        if(dep[a]>dep[b]){
            swap(a,b);
        }
        for(int i=19;i>=0;i--){
            if(dep[as[b][i]]>=dep[a]){
                b=as[b][i];
            }
        }
        for(int i=19;i>=0;i--){
            if(as[b][i]!=as[a][i]){
                a=as[a][i];
                b=as[b][i];
            }
        }
        return as[a][0];
    }
}tr;

struct DSU{
    vector<int> bo,tag;
    int sz=0;
    vector<int> deg;
    void init(int n){
        bo.resize(n);
        iota(bo.begin(),bo.end(),0);
        tag.resize(n);
        deg.resize(n);
        sz=n;
    }
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    void merge(int x,int y,int cnt){
        deg[x]++;
        deg[y]++;
        int u=(deg[x]>=3 || deg[y]>=3);
        x=find(x);
        y=find(y);
        if(x==y){
            if(tag[x]==0){
                tag[x]=1;
                tr.val[x]=cnt;
            }
            return;
        }
        tag.push_back(0);
        bo.push_back(sz);
        deg.push_back(0);
        bo[x]=bo[y]=sz;
        tag[sz]|=tag[x];
        tag[sz]|=tag[y];
        tag[sz]|=u;
        if(!tag[sz]){
            cnt=2e9;
        }
        tr.add(cnt);
        tr.eg(sz,x);
        tr.eg(sz,y);
        sz++;
    }
}dsu;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    dsu.init(n);
    tr.init(n);
    vector<pair<int,pair<int,int> > > eg;
    for(int i=0;i<m;i++){
        eg.push_back({w[i],{u[i],v[i]}});
    }
    sort(eg.begin(),eg.end());
    for(auto h:eg){
        dsu.merge(h.sc.fs,h.sc.sc,h.fs);
    }
    tr.tag=dsu.tag;
    tr.dfs(tr.sz-1,tr.sz-1);
}

int getMinimumFuelCapacity(int x, int y) {
    int u=tr.lca(x,y);
    if(tr.val[u]>1.5e9){
        return -1;
    }
    return tr.val[u];
}

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