Submission #429647

#	Time	Username	Problem	Language	Result	Execution time	Memory
429647		Peti	Swapping Cities (APIO20_swap)	C++14	100 / 100	523 ms	57384 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"

using namespace std;

const int logn = 20;

struct node{
    int l = -1, r = -1, os = -1, be, ki, ert = 0;
    bool jo = false;
};

struct el{
    int u, v, c;
    bool operator < (const el &e) const{
        return c < e.c;
    }
};

vector<node> g;

struct union_find{
    vector<int> vos, vm, ind, fok;
    vector<bool> jo;

    void init(int n){
        vm.assign(n, 1);
        vos.assign(n, -1);
        fok.assign(n, 0);
        jo.assign(n, false);
        ind.resize(n);
        iota(ind.begin(), ind.end(), 0);
    }

    int os(int x){
        return (vos[x] == -1 ? x : vos[x] = os(vos[x]));
    }

    bool unio(int a, int b, int ert){
        //cout<<"union "<<a<<" "<<b<<"\n";
        fok[a]++;
        fok[b]++;
        bool kesz = fok[a] > 2 || fok[b] > 2;
        a = os(a);
        b = os(b);

        if(a == b){
            jo[a] = true;
            g.push_back({ind[a], -1, -1, 0, 0, ert, jo[a]});
            ind[a] = (int)g.size()-1;
            return false;
        }
        if(vm[a] < vm[b]) swap(a, b);

        vos[b] = a;
        vm[a] += (int)(vm[a] == vm[b]);
        /*cout<<"new node: "<<ind[a]<<" "<<ind[b]<<" | "<<g.size()<<"\n";
        cout<<"can solve: "<<jo[a]<<" "<<jo[b]<<" "<<kesz<<"\n";*/
        if(jo[b] || kesz)
            jo[a] = true;
        g.push_back({ind[a], ind[b], -1, 0, 0, ert, jo[a]});
        ind[a] = (int)g.size()-1;
        return true;
    }
};

int ido = 0;
void bejar(int akt, int os){
    //cout<<akt<<" bejar\n";
    if(akt == -1) return;
    g[akt].os = os;
    g[akt].be = ido++;
    bejar(g[akt].l, akt);
    bejar(g[akt].r, akt);
    g[akt].ki = ido++;
}

vector<vector<int>> lca;
union_find csop;
int n;

int ose(int a, int b){
    return g[a].be <= g[b].be && g[b].ki <= g[a].ki;
}

int get_lca(int a, int b){
    if(ose(a, b))
        return a;
    for(int i = logn-1; i >= 0; i--)
        if(!ose(lca[a][i], b))
            a = lca[a][i];
    return lca[a][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    vector<el> v(M);
    for(int i = 0; i < M; i++)
        v[i] = {U[i], V[i], W[i]};
    sort(v.begin(), v.end());


    g.assign(N, node());
    csop.init(N);
    for(el e : v)
        csop.unio(e.u, e.v, e.c);
    n = (int)g.size();
    bejar(n-1, n-1);

    /*cout<<n<<" g size\n";
    for(int i = 0; i < n; i++)
        cout<<g[i].os<<" ";
    cout<<"\n";*/

    lca.assign(n, vector<int>(logn, n-1));
    for(int i = 0; i < n; i++)
        lca[i][0] = g[i].os;

    for(int j = 1; j < logn; j++)
        for(int i = 0; i < n; i++)
            lca[i][j] = lca[lca[i][j-1]][j-1];
}

int getMinimumFuelCapacity(int X, int Y) {
    int p = get_lca(X, Y);

    if(g[p].jo)
        return g[p].ert;

    for(int i = logn-1; i >= 0; i--)
        if(!g[lca[p][i]].jo)
            p = lca[p][i];
    p = lca[p][0];

    if(g[p].jo)
        return g[p].ert;
    return -1;
}

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