oj.uz

Submission #972848

# Submission time Handle Problem Language Result Execution time Memory
972848 2024-05-01T09:03:53 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 457 ms 524292 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[2 * 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) {
    mark[u] = true;
    tin[u] = ++timer;
    for(int v : g[u]) {
        dfs(v);
        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);
    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


3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 256596 KB Output is correct
2 Correct 171 ms 256592 KB Output is correct
3 Correct 173 ms 256596 KB Output is correct
4 Correct 177 ms 256728 KB Output is correct
5 Correct 191 ms 256860 KB Output is correct
6 Correct 173 ms 256784 KB Output is correct
7 Correct 176 ms 256852 KB Output is correct
8 Correct 173 ms 257364 KB Output is correct
9 Correct 219 ms 270640 KB Output is correct
10 Correct 230 ms 273768 KB Output is correct
11 Correct 230 ms 273356 KB Output is correct
12 Correct 238 ms 274964 KB Output is correct
13 Runtime error 457 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 216 ms 256596 KB Output is correct
2 Correct 171 ms 256592 KB Output is correct
3 Runtime error 441 ms 524292 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 216 ms 256596 KB Output is correct
2 Correct 171 ms 256592 KB Output is correct
3 Correct 173 ms 256596 KB Output is correct
4 Correct 177 ms 256728 KB Output is correct
5 Correct 191 ms 256860 KB Output is correct
6 Correct 173 ms 256784 KB Output is correct
7 Correct 176 ms 256852 KB Output is correct
8 Correct 173 ms 257364 KB Output is correct
9 Correct 175 ms 258640 KB Output is correct
10 Incorrect 192 ms 256848 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 258640 KB Output is correct
2 Correct 216 ms 256596 KB Output is correct
3 Correct 171 ms 256592 KB Output is correct
4 Correct 173 ms 256596 KB Output is correct
5 Correct 177 ms 256728 KB Output is correct
6 Correct 191 ms 256860 KB Output is correct
7 Correct 173 ms 256784 KB Output is correct
8 Correct 176 ms 256852 KB Output is correct
9 Correct 173 ms 257364 KB Output is correct
10 Correct 219 ms 270640 KB Output is correct
11 Correct 230 ms 273768 KB Output is correct
12 Correct 230 ms 273356 KB Output is correct
13 Correct 238 ms 274964 KB Output is correct
14 Runtime error 457 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 216 ms 256596 KB Output is correct
2 Correct 171 ms 256592 KB Output is correct
3 Correct 173 ms 256596 KB Output is correct
4 Correct 177 ms 256728 KB Output is correct
5 Correct 191 ms 256860 KB Output is correct
6 Correct 173 ms 256784 KB Output is correct
7 Correct 176 ms 256852 KB Output is correct
8 Correct 173 ms 257364 KB Output is correct
9 Correct 219 ms 270640 KB Output is correct
10 Correct 230 ms 273768 KB Output is correct
11 Correct 230 ms 273356 KB Output is correct
12 Correct 238 ms 274964 KB Output is correct
13 Runtime error 457 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 175 ms 258640 KB Output is correct
2 Correct 216 ms 256596 KB Output is correct
3 Correct 171 ms 256592 KB Output is correct
4 Correct 173 ms 256596 KB Output is correct
5 Correct 177 ms 256728 KB Output is correct
6 Correct 191 ms 256860 KB Output is correct
7 Correct 173 ms 256784 KB Output is correct
8 Correct 176 ms 256852 KB Output is correct
9 Correct 173 ms 257364 KB Output is correct
10 Correct 219 ms 270640 KB Output is correct
11 Correct 230 ms 273768 KB Output is correct
12 Correct 230 ms 273356 KB Output is correct
13 Correct 238 ms 274964 KB Output is correct
14 Runtime error 457 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -