Submission #558033

#	Time	Username	Problem	Language	Result	Execution time	Memory
558033		InternetPerson10	Swapping Cities (APIO20_swap)	C++17	100 / 100	477 ms	50420 KiB

swap

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

using namespace std;

int BIG = 1e9 + 7; // 
int second[100001];
int third[100001];
int depth[100001];
int parent[100001];
int parWeight[100001];
int liftWt[100001][20]; // The maximum of weights when going above
int liftVal[100001][20]; // The vertex that is 2^i above
int liftMin[100001][20]; // The minimum of the thirds up to 2^i above

vector<vector<pair<int, int>>> adj;

void dfs(int n, int par = -1) {
    for(auto p : adj[n]) {
        int ch, w;
        tie(ch, w) = p;
        if(ch == par) continue;
        parWeight[ch] = w;
        parent[ch] = n;
        depth[ch] = depth[n] + 1;
        dfs(ch, n);
    }
}

struct dsu {
    vector<int> par, siz, lin, linen;
    void init(int n) {
        par.resize(n);
        siz.resize(n, 1);
        lin.resize(n, BIG);
        linen.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(par[x] == x) return x;
        int g = get(par[x]);
        if(lin[x] != BIG) return par[x] = g;
        if(lin[par[x]] != BIG) {
            lin[x] = lin[par[x]];
            linen[x] = 0;
        }
        return par[x] = g;
    }
    bool unite(int x, int y, int w) {
        int gx = get(x), gy = get(y);
        if(gx == gy) {
            if(lin[gx] == BIG) {
                lin[gx] = w;
                linen[gx] = 0;
            }
            return false;
        }
        // Connecting a line and a line, becomes a line
        if(lin[gx] == BIG && lin[gy] == BIG && linen[x] && linen[y]) {
            if(siz[gx] != 1) linen[x] = 0;
            if(siz[gy] != 1) linen[y] = 0;
        }
        // Connecting a line and a line, doesn't become a line
        else {
            lin[gx] = min(lin[gx], w);
            lin[gy] = min(lin[gy], w);
            linen[x] = linen[y] = 0;
        }
        x = gx; y = gy;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

dsu uf;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<pair<int, pair<int, int>>> edges(M);
    for(int i = 0; i < N; i++) {
        depth[i] = 0;
        second[i] = BIG;
        third[i] = -1;
        parent[i] = 0;
    }
    adj.resize(N);
    for(int i = 0; i < M; i++) {
        edges[i] = {W[i], {U[i], V[i]}};
    }
    sort(edges.begin(), edges.end());
    uf.init(N);
    for(auto [w, p] : edges) {
        int u, v;
        tie(u, v) = p;
        if(third[u] < 0) {
            third[u]--;
            if(third[u] == -3) second[u] = w;
            if(third[u] == -4) third[u] = w;
        }
        if(third[v] < 0) {
            third[v]--;
            if(third[v] == -3) second[v] = w;
            if(third[v] == -4) third[v] = w;
        }
        if(uf.unite(u, v, w)) {
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }
    for(int i = 0; i < N; i++) {
        uf.get(i);
        // cout << i << ' ' << uf.lin[i] << endl;
        if(third[i] < 0) third[i] = BIG;
    }
    dfs(0);
    for(int i = 0; i < 20; i++) {
        liftWt[0][i] = liftVal[0][i] = 0;
        liftMin[0][i] = third[0];
    }
    for(int x = 1; x < N; x++) {
        liftWt[x][0] = parWeight[x];
        liftVal[x][0] = parent[x];
        liftMin[x][0] = min(third[x], third[parent[x]]);
    }
    for(int i = 1; i < 20; i++) {
        for(int x = 1; x < N; x++) {
            int xUp = liftVal[x][i-1];
            liftWt[x][i] = max(liftWt[x][i-1], liftWt[xUp][i-1]);
            liftVal[x][i] = liftVal[xUp][i-1];
            liftMin[x][i] = min(liftMin[x][i-1], liftMin[xUp][i-1]);
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    int weightMax = 0, thirdMin = BIG;
    int secondx = uf.lin[x], secondy = uf.lin[y];
    if(depth[x] > depth[y]) swap(x, y);
    if(depth[x] < depth[y]) {
        int g = depth[y] - depth[x];
        for(int i = 0; i < 20; i++) {
            if(g & (1 << i)) {
                weightMax = max(weightMax, liftWt[y][i]);
                thirdMin = min(thirdMin, liftMin[y][i]);
                y = liftVal[y][i];
            }
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(liftVal[x][i] != liftVal[y][i]) {
            weightMax = max(weightMax, liftWt[x][i]);
            thirdMin = min(thirdMin, liftMin[x][i]);
            x = liftVal[x][i];
            weightMax = max(weightMax, liftWt[y][i]);
            thirdMin = min(thirdMin, liftMin[y][i]);
            y = liftVal[y][i];
        }
        if(i == 0 && x != y) {
            weightMax = max(weightMax, liftWt[x][i]);
            thirdMin = min(thirdMin, liftMin[x][i]);
            x = liftVal[x][i];
            weightMax = max(weightMax, liftWt[y][i]);
            thirdMin = min(thirdMin, liftMin[y][i]);
            y = liftVal[y][i];
        }
    }
    int ans = max(weightMax, min(thirdMin, min(secondx, secondy)));
    if(ans == BIG) return -1;
    return ans;
}

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