oj.uz

Submission #972819

# Submission time Handle Problem Language Result Execution time Memory
972819 2024-05-01T08:26:25 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 505 ms 524288 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

int tsz;

struct DSU {
    int n;
    vector<int> parent, sz;
    vector<bool> chain;
    vector<vector<int>> comp;
    vector<int> id;
    DSU(int _n) {
        n = _n;
        parent.resize(n);
        sz.resize(n);
        comp.resize(n);
        chain.resize(n);
        id.resize(n);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
            chain[i] = true;
            comp[i].push_back(i);
            id[i] = i;
        }
    }
    int find_parent(int u) {
        if(parent[u] == u) return u;
        return parent[u] = find_parent(parent[u]);
    }
    bool check(int u, int v) {
        u = find_parent(u);
        v = find_parent(v);
        return u == v;
    }
    void join(int u, int v) {
        u = find_parent(u);
        v = find_parent(v);
        if(sz[u] > sz[v]) swap(u, v);
        for(int i : comp[u]) comp[v].push_back(i);
        comp[u].clear();
        parent[u] = v;
        id[v] = tsz;
    }
    void update_chain_state(int u) {
        u = find_parent(u);
        chain[u] = false;
    }
    int get_size(int u) {
        u = find_parent(u);
        return sz[u];
    }
};

const int N = 5e5 + 10, LOG = 19;
bool leaf[N];
DSU dsu(N), tree(2 * N);
int order[N];
vector<int> g[2 * N];
int up[2 * N][LOG + 1];
int root;
int timer;
int tin[2 * N], tout[2 * N];
int ans[2 * N];
bool mark[2 * N];

void dfs(int u, int par) {
    mark[u] = true;
    tin[u] = ++timer;
    for(int v : g[u]) {
        dfs(v, u);
        up[v][0] = u;
    }
    tout[u] = ++timer;
}

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int LCA(int u, int v) {
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j = LOG - 1; j >= 0; j--) {
        if(up[u][j] == 0) continue;
        if(is_ancestor(up[u][j], v)) continue;
        u = up[u][j];
    }
    return up[u][0];
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    for(int i = 0; i < N; i++) leaf[i] = true;
    tsz = n;
    for(int i = 0; i < m; i++) order[i] = i;
    sort(order, order + m, [&](int i, int j) { return W[i] < W[j]; });
    for(int i = 0; i < m; i++) {
        int u = U[order[i]], v = V[order[i]];
        if(dsu.check(u, v)) {
            int par = dsu.find_parent(u);
            if(dsu.chain[par]) {
                for(int j : dsu.comp[par]) {
                    g[tsz].push_back(j);
                    tree.join(tsz, j);
                }
                ans[tsz] = W[order[i]];
                tsz++;
                dsu.update_chain_state(par);
            }
        } else {
            if(!dsu.chain[dsu.find_parent(u)] || !dsu.chain[dsu.find_parent(v)]) {
                if(dsu.chain[dsu.find_parent(u)]) {
                    for(int j : dsu.comp[dsu.find_parent(u)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                } else {
                    g[tsz].push_back(dsu.id[dsu.find_parent(u)]);
                    tree.join(tsz, dsu.id[dsu.find_parent(u)]);
                }
                if(dsu.chain[dsu.find_parent(v)]) {
                    for(int j : dsu.comp[dsu.find_parent(v)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                } else {
                    g[tsz].push_back(dsu.id[dsu.find_parent(v)]);
                    tree.join(tsz, dsu.id[dsu.find_parent(v)]);
                }
                dsu.join(u, v);
                ans[tsz] = W[order[i]];
                tsz++;
            } else {
                if(leaf[u] && leaf[v]) {
                    if(dsu.get_size(u) > 1) leaf[u] = false;
                    if(dsu.get_size(v) > 1) leaf[v] = false;
                    dsu.join(u, v);
                } else {
                    for(int j : dsu.comp[dsu.find_parent(u)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                    for(int j : dsu.comp[dsu.find_parent(v)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                    dsu.join(u, v);
                    ans[tsz] = W[order[i]];
                    tsz++;
                    dsu.update_chain_state(u);
                }
            }
        }
    }
//    for(int i = 0; i < tsz; i++) {
//        cout << i << ": ";
//        for(int j : g[i]) cout << j << " ";
//        cout << "\n";
//    }
    root = tsz - 1;
    for(int i = root; i >= 0; i--) if(!mark[i]) dfs(i, -1);
    for(int j = 1; j < LOG; j++) for(int i = 0; i <= root; i++) up[i][j] = up[up[i][j - 1]][j - 1];
}

int getMinimumFuelCapacity(int X, int Y) {
    if(!tree.check(X, Y)) return -1;
    return ans[LCA(X, Y)];
}

/*

5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1




*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 131664 KB Output is correct
2 Correct 102 ms 131536 KB Output is correct
3 Correct 86 ms 131640 KB Output is correct
4 Correct 94 ms 131664 KB Output is correct
5 Correct 91 ms 131708 KB Output is correct
6 Correct 90 ms 131668 KB Output is correct
7 Correct 102 ms 131536 KB Output is correct
8 Correct 95 ms 132176 KB Output is correct
9 Correct 138 ms 144588 KB Output is correct
10 Correct 162 ms 148068 KB Output is correct
11 Correct 160 ms 147700 KB Output is correct
12 Correct 158 ms 148940 KB Output is correct
13 Runtime error 487 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 131664 KB Output is correct
2 Correct 102 ms 131536 KB Output is correct
3 Runtime error 505 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 131664 KB Output is correct
2 Correct 102 ms 131536 KB Output is correct
3 Correct 86 ms 131640 KB Output is correct
4 Correct 94 ms 131664 KB Output is correct
5 Correct 91 ms 131708 KB Output is correct
6 Correct 90 ms 131668 KB Output is correct
7 Correct 102 ms 131536 KB Output is correct
8 Correct 95 ms 132176 KB Output is correct
9 Correct 89 ms 133584 KB Output is correct
10 Incorrect 93 ms 131664 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 133584 KB Output is correct
2 Correct 108 ms 131664 KB Output is correct
3 Correct 102 ms 131536 KB Output is correct
4 Correct 86 ms 131640 KB Output is correct
5 Correct 94 ms 131664 KB Output is correct
6 Correct 91 ms 131708 KB Output is correct
7 Correct 90 ms 131668 KB Output is correct
8 Correct 102 ms 131536 KB Output is correct
9 Correct 95 ms 132176 KB Output is correct
10 Correct 138 ms 144588 KB Output is correct
11 Correct 162 ms 148068 KB Output is correct
12 Correct 160 ms 147700 KB Output is correct
13 Correct 158 ms 148940 KB Output is correct
14 Runtime error 487 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 131664 KB Output is correct
2 Correct 102 ms 131536 KB Output is correct
3 Correct 86 ms 131640 KB Output is correct
4 Correct 94 ms 131664 KB Output is correct
5 Correct 91 ms 131708 KB Output is correct
6 Correct 90 ms 131668 KB Output is correct
7 Correct 102 ms 131536 KB Output is correct
8 Correct 95 ms 132176 KB Output is correct
9 Correct 138 ms 144588 KB Output is correct
10 Correct 162 ms 148068 KB Output is correct
11 Correct 160 ms 147700 KB Output is correct
12 Correct 158 ms 148940 KB Output is correct
13 Runtime error 487 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 133584 KB Output is correct
2 Correct 108 ms 131664 KB Output is correct
3 Correct 102 ms 131536 KB Output is correct
4 Correct 86 ms 131640 KB Output is correct
5 Correct 94 ms 131664 KB Output is correct
6 Correct 91 ms 131708 KB Output is correct
7 Correct 90 ms 131668 KB Output is correct
8 Correct 102 ms 131536 KB Output is correct
9 Correct 95 ms 132176 KB Output is correct
10 Correct 138 ms 144588 KB Output is correct
11 Correct 162 ms 148068 KB Output is correct
12 Correct 160 ms 147700 KB Output is correct
13 Correct 158 ms 148940 KB Output is correct
14 Runtime error 487 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -