Submission #581498

#	Time	Username	Problem	Language	Result	Execution time	Memory
581498		training4usaco	Swapping Cities (APIO20_swap)	C++11	0 / 100	4 ms	7380 KiB

swap

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100005
#define MAXM 200005
#define MAXS (MAXN + MAXM + 1)
#define LN 20
#define INF 1000000007

struct Edge {
    int a, b, weight;

    bool operator<(const Edge &other) const {
        return weight < other.weight;
    }
};

struct DSU {
    vector<int> parent;
    vector<int> sizes;

    int getRoot(int node) {
        if(node == parent[node]) {
            return node;
        }

        return parent[node] = getRoot(node);
    }

    DSU(int n) {
        parent.resize(n);
        sizes.resize(n);

        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            sizes[i] = 1;
        }
    }

    DSU() {}
};

int n, m;
bool swappable[MAXS];
int nodeweight[MAXS];
int indegree[MAXN];
vector<int> krtadj[MAXS];
Edge edges[MAXM];
int up[MAXS][LN];
int depth[MAXS];
DSU dsu;
int krtsize, krtnode;

void dfs(int node, int par, int dep) {
    depth[node] = dep;

    for(auto next : krtadj[node]) {
        if(next != par) {
            up[0][next] = node;
            dfs(next, node, dep + 1);
        }
    }
}

int LCA(int a, int b) {
    if(depth[a] < depth[b]) {
        swap(a, b);
    }

    for(int i = LN - 1; i >= 0; --i) {
        if(depth[up[i][a]] >= depth[b]) {
            a = up[i][a];
        }
    }

    if (a == b) {
        return a;
    }

    for(int i = LN - 1; i >= 0; --i) {
        if(up[i][a] != up[i][b]) {
            a = up[i][a];
            a = up[i][b];
        }
    }

    return up[0][a];
}

void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
    n = _n;
    m = _m;

    for(int i = 0; i < m; ++i) {
        edges[i] = {u[i] + 1, v[i] + 1, w[i]};
    }

    sort(edges + 1, edges + m + 1);

    krtsize = n + m + 1;
    krtnode = n + 1;

    dsu = DSU(krtsize + 1);
    for(int i = 1; i <= m; ++i) {
        Edge edge = edges[i];
        int a = edge.a; int b = edge.b; int weight = edge.weight;
        
        ++indegree[a]; ++indegree[b];

        int aroot = dsu.getRoot(a);
        int broot = dsu.getRoot(b);

        if(aroot == broot) {
            if(!swappable[aroot]) {
                swappable[aroot] = true;
                nodeweight[aroot] = weight;
            }
        }
        else {
            krtadj[krtnode].push_back(aroot);
            krtadj[krtnode].push_back(broot);
            nodeweight[krtnode] = weight;

            if(indegree[a] > 2 || indegree[b] > 2 || swappable[aroot] || swappable[broot]) {
                swappable[krtnode] = true;
            }
            
            dsu.parent[aroot] = krtnode;
            dsu.parent[broot] = krtnode;

            ++krtnode;
        }
    }

    depth[0] = -1;
    dfs(krtnode - 1, -1, 0);

    for(int i = 1; i < LN; ++i) {
        for(int j = 1; j < n + m + 1; ++j) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    ++x; ++y;
    
    int closestswappable = LCA(x, y);

    if(swappable[closestswappable]) {
        return nodeweight[closestswappable];
    }

    for(int i = LN - 1; i >= 0; --i) {
        int ancestor = up[i][closestswappable];
        if(ancestor != 0 && !swappable[ancestor]) {
            closestswappable = ancestor;
        }
    }

    closestswappable = up[0][closestswappable];

    if(swappable[closestswappable]) {
        return nodeweight[closestswappable];
    }
    return -1;
}

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