oj.uz

Submission #972820

# Submission time Handle Problem Language Result Execution time Memory
972820 2024-05-01T08:27:16 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 464 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 = 1e6 + 10, LOG = 20;
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 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 183 ms 248260 KB Output is correct
4 Correct 183 ms 248400 KB Output is correct
5 Correct 181 ms 248344 KB Output is correct
6 Correct 186 ms 248400 KB Output is correct
7 Correct 186 ms 248372 KB Output is correct
8 Correct 192 ms 249424 KB Output is correct
9 Correct 240 ms 262408 KB Output is correct
10 Correct 245 ms 265780 KB Output is correct
11 Correct 248 ms 265504 KB Output is correct
12 Correct 251 ms 266828 KB Output is correct
13 Runtime error 463 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 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Runtime error 464 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 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 183 ms 248260 KB Output is correct
4 Correct 183 ms 248400 KB Output is correct
5 Correct 181 ms 248344 KB Output is correct
6 Correct 186 ms 248400 KB Output is correct
7 Correct 186 ms 248372 KB Output is correct
8 Correct 192 ms 249424 KB Output is correct
9 Correct 190 ms 248280 KB Output is correct
10 Incorrect 186 ms 248656 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 248280 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 187 ms 248400 KB Output is correct
4 Correct 183 ms 248260 KB Output is correct
5 Correct 183 ms 248400 KB Output is correct
6 Correct 181 ms 248344 KB Output is correct
7 Correct 186 ms 248400 KB Output is correct
8 Correct 186 ms 248372 KB Output is correct
9 Correct 192 ms 249424 KB Output is correct
10 Correct 240 ms 262408 KB Output is correct
11 Correct 245 ms 265780 KB Output is correct
12 Correct 248 ms 265504 KB Output is correct
13 Correct 251 ms 266828 KB Output is correct
14 Runtime error 463 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 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 183 ms 248260 KB Output is correct
4 Correct 183 ms 248400 KB Output is correct
5 Correct 181 ms 248344 KB Output is correct
6 Correct 186 ms 248400 KB Output is correct
7 Correct 186 ms 248372 KB Output is correct
8 Correct 192 ms 249424 KB Output is correct
9 Correct 240 ms 262408 KB Output is correct
10 Correct 245 ms 265780 KB Output is correct
11 Correct 248 ms 265504 KB Output is correct
12 Correct 251 ms 266828 KB Output is correct
13 Runtime error 463 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 190 ms 248280 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 187 ms 248400 KB Output is correct
4 Correct 183 ms 248260 KB Output is correct
5 Correct 183 ms 248400 KB Output is correct
6 Correct 181 ms 248344 KB Output is correct
7 Correct 186 ms 248400 KB Output is correct
8 Correct 186 ms 248372 KB Output is correct
9 Correct 192 ms 249424 KB Output is correct
10 Correct 240 ms 262408 KB Output is correct
11 Correct 245 ms 265780 KB Output is correct
12 Correct 248 ms 265504 KB Output is correct
13 Correct 251 ms 266828 KB Output is correct
14 Runtime error 463 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -