Submission #1106500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106500		vladilius	Swapping Cities (APIO20_swap)	C++17	13 / 100	215 ms	49296 KiB

swap

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int inf = 3e5;
const int infv = numeric_limits<int> :: max();

struct dsu{
    vector<int> p, d, A;
    vector<vector<int>> g;
    vector<bool> f;
    int n, cc, k;
    void init(int ns){
        n = ns;
        d.resize(n + 1);
        p.resize(inf + 1);
        f.resize(inf + 1);
        for (int i = 1; i <= inf; i++){
            p[i] = i;
        }
        cc = n;
        g.resize(inf + 1);
        A.assign(inf + 1, infv);
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y, int w){
        int a = get(x), b = get(y);
        if (a == b){
            if (!f[a]){
                cc++;
                p[a] = cc;
                A[cc] = w;
                g[cc].pb(a);
            }
            return;
        }
        
        if (f[a] || f[b] || d[x] == 2 || d[y] == 2){
            cc++;
            p[a] = p[b] = cc;
            A[cc] = w;
            g[cc].pb(a);
            g[cc].pb(b);
            f[b] = 1;
        }
        else {
            cc++;
            p[a] = p[b] = cc;
            g[cc].pb(a);
            g[cc].pb(b);
            d[x]++; d[y]++;
        }
    }
    vector<int> tin, tout, out;
    vector<vector<int>> pw;
    int lg, timer;
    void fill(int v, int pr){
        tin[v] = ++timer;
        out[v] = min(out[pr], A[v]);
        pw[v][0] = pr;
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (int i: g[v]){
            fill(i, v);
        }
        tout[v] = timer;
    }
    void build(){
        tin.resize(cc + 1);
        tout.resize(cc + 1);
        lg = log2(cc);
        pw.resize(cc + 1);
        for (int i = 1; i <= cc; i++){
            pw[i].resize(lg + 1);
        }
        timer = 0;
        out.assign(inf + 1, infv);
        fill(cc, cc);
        
        for (int i = 1; i <= inf; i++){
            if (out[i] == infv){
                out[i] = -1;
            }
        }
    }
    bool check(int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    }
    int lca(int x, int y){
        for (int i = lg; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    }
    int get(int x, int y){
        return out[lca(x, y)];
    }
};

dsu T;
int n, m;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
    n = N; m = M;
    vector<arr3> ed;
    for (int i = 0; i < m; i++){
        ed.pb({W[i], U[i] + 1, V[i] + 1});
    }
    sort(ed.begin(), ed.end());
    T.init(n);
    for (auto [f, x, y]: ed){
        T.unite(x, y, f);
    }
    T.build();
}

int getMinimumFuelCapacity(int x, int y){
    x++; y++;
    return T.get(x, y);
}

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