Submission #581555

#	Time	Username	Problem	Language	Result	Execution time	Memory
581555		training4usaco	Swapping Cities (APIO20_swap)	C++11	0 / 100	176 ms	28212 KiB

swap

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

using namespace std;

#define int long long

#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(parent[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) {
    // cout << "depth of " << a << ", " << b << ": ";
    // cout << depth[a] << " " << depth[b] << endl;
    if(depth[a] < depth[b]) {
        swap(a, b);
    }

    for(int i = LN - 1; i >= 0; --i) {
        if(depth[up[i][a]] >= depth[b]) {
            // cout << "a" << endl;
            a = up[i][a];
        }
    }
    // cout << "same depth" << endl;

    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];
        }
    }

    // cout << "done" << endl;

    return up[0][a];
}

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

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

    sort(edges, edges + m);

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

    dsu = DSU(krtsize);
    // cout << "finsiehd init dsu" << endl; 
    for(int i = 0; i < m; ++i) {
        Edge edge = edges[i];
        int a = edge.a; int b = edge.b; int weight = edge.weight;
        
        ++indegree[a]; ++indegree[b];

        // cout << "finished reading in edges" << endl;

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

        // cout << "finished getting root" << endl;

        if(aroot == broot) {
            // cout << "merging same component" << endl;
            if(!swappable[aroot]) {
                swappable[aroot] = true;
                nodeweight[aroot] = weight;
            }
        }
        else {
            // cout << "different components" << endl;
            // cout << "nodes: " << a << " " << b << endl;
            // cout << "roots: " << aroot << " " << broot << endl;
            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;
            }
            
            // cout << "merging" << endl;
            dsu.parent[aroot] = krtnode;
            dsu.parent[broot] = krtnode;
            // cout << "finished merging" << endl;
            ++krtnode;
        }
    }

    // cout << "finished constructing krt" << endl;
    depth[0] = -1;
    dfs(krtnode - 1, -1, 0);

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

    // cout << "finished init for lca" << endl;
}

int getMinimumFuelCapacity(int32_t x, int32_t y) {
    ++x; ++y;
    
    int closestswappable = LCA(x, y);
    // cout << "got lca" << endl;

    if(swappable[closestswappable]) {
        // cout << "lca was swappable" << endl;
        return nodeweight[closestswappable];
    }

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

    // cout << "found one lower" << endl;

    closestswappable = up[0][closestswappable];

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

// signed main() {
//     int n, m;
//     cin >> n >> m;
    
//     vector<int> u(m);
//     vector<int> v(m);
//     vector<int> w(m);

//     for(int i = 0; i < m; ++i) {
//         cin >> u[i] >> v[i] >> w[i];
//     }

//     init(n, m, u, v, w);

//     int q;
//     cin >> q;
//     while(q--) {
//         int a, b;
//         cin >> a >> b;
//         cout << getMinimumFuelCapacity(a, b) << endl;
//     }
// }

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