oj.uz

Submission #581552

# Submission time Handle Problem Language Result Execution time Memory
581552 2022-06-22T17:58:03 Z training4usaco Swapping Cities (APIO20_swap) C++11
0 / 100
 193 ms 26484 KB 
#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(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(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, edges + m);

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

    dsu = DSU(krtsize + 1);
    // 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(int x, int 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;
}

// int 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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 6 ms 7364 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7392 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 54 ms 17224 KB Output is correct
10 Correct 70 ms 19468 KB Output is correct
11 Correct 74 ms 19360 KB Output is correct
12 Correct 86 ms 20040 KB Output is correct
13 Correct 61 ms 21328 KB Output is correct
14 Correct 70 ms 17608 KB Output is correct
15 Correct 193 ms 23652 KB Output is correct
16 Correct 167 ms 23336 KB Output is correct
17 Correct 186 ms 24136 KB Output is correct
18 Correct 168 ms 25396 KB Output is correct
19 Incorrect 88 ms 13296 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Incorrect 167 ms 26484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 6 ms 7364 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7392 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7364 KB Output is correct
10 Incorrect 5 ms 7380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 6 ms 7364 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7392 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 54 ms 17224 KB Output is correct
11 Correct 70 ms 19468 KB Output is correct
12 Correct 74 ms 19360 KB Output is correct
13 Correct 86 ms 20040 KB Output is correct
14 Correct 61 ms 21328 KB Output is correct
15 Incorrect 5 ms 7380 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 6 ms 7364 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7392 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 54 ms 17224 KB Output is correct
10 Correct 70 ms 19468 KB Output is correct
11 Correct 74 ms 19360 KB Output is correct
12 Correct 86 ms 20040 KB Output is correct
13 Correct 61 ms 21328 KB Output is correct
14 Correct 70 ms 17608 KB Output is correct
15 Correct 193 ms 23652 KB Output is correct
16 Correct 167 ms 23336 KB Output is correct
17 Correct 186 ms 24136 KB Output is correct
18 Correct 168 ms 25396 KB Output is correct
19 Incorrect 167 ms 26484 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 6 ms 7364 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7392 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 54 ms 17224 KB Output is correct
11 Correct 70 ms 19468 KB Output is correct
12 Correct 74 ms 19360 KB Output is correct
13 Correct 86 ms 20040 KB Output is correct
14 Correct 61 ms 21328 KB Output is correct
15 Correct 70 ms 17608 KB Output is correct
16 Correct 193 ms 23652 KB Output is correct
17 Correct 167 ms 23336 KB Output is correct
18 Correct 186 ms 24136 KB Output is correct
19 Correct 168 ms 25396 KB Output is correct
20 Incorrect 167 ms 26484 KB Output isn't correct
21 Halted 0 ms 0 KB -