oj.uz

Submission #972859

# Submission time Handle Problem Language Result Execution time Memory
972859 2024-05-01T09:09:51 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 467 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[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;
    assert(LCA(X, Y) > 0 && LCA(X, Y) <= root);
    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 200 ms 256756 KB Output is correct
2 Correct 174 ms 256612 KB Output is correct
3 Correct 191 ms 256596 KB Output is correct
4 Correct 173 ms 256848 KB Output is correct
5 Correct 205 ms 256704 KB Output is correct
6 Correct 190 ms 256816 KB Output is correct
7 Correct 185 ms 256888 KB Output is correct
8 Correct 187 ms 257360 KB Output is correct
9 Correct 241 ms 269960 KB Output is correct
10 Correct 268 ms 273008 KB Output is correct
11 Correct 242 ms 272820 KB Output is correct
12 Correct 243 ms 273860 KB Output is correct
13 Runtime error 453 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 200 ms 256756 KB Output is correct
2 Correct 174 ms 256612 KB Output is correct
3 Runtime error 467 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 200 ms 256756 KB Output is correct
2 Correct 174 ms 256612 KB Output is correct
3 Correct 191 ms 256596 KB Output is correct
4 Correct 173 ms 256848 KB Output is correct
5 Correct 205 ms 256704 KB Output is correct
6 Correct 190 ms 256816 KB Output is correct
7 Correct 185 ms 256888 KB Output is correct
8 Correct 187 ms 257360 KB Output is correct
9 Correct 182 ms 258756 KB Output is correct
10 Incorrect 186 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 182 ms 258756 KB Output is correct
2 Correct 200 ms 256756 KB Output is correct
3 Correct 174 ms 256612 KB Output is correct
4 Correct 191 ms 256596 KB Output is correct
5 Correct 173 ms 256848 KB Output is correct
6 Correct 205 ms 256704 KB Output is correct
7 Correct 190 ms 256816 KB Output is correct
8 Correct 185 ms 256888 KB Output is correct
9 Correct 187 ms 257360 KB Output is correct
10 Correct 241 ms 269960 KB Output is correct
11 Correct 268 ms 273008 KB Output is correct
12 Correct 242 ms 272820 KB Output is correct
13 Correct 243 ms 273860 KB Output is correct
14 Runtime error 453 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 200 ms 256756 KB Output is correct
2 Correct 174 ms 256612 KB Output is correct
3 Correct 191 ms 256596 KB Output is correct
4 Correct 173 ms 256848 KB Output is correct
5 Correct 205 ms 256704 KB Output is correct
6 Correct 190 ms 256816 KB Output is correct
7 Correct 185 ms 256888 KB Output is correct
8 Correct 187 ms 257360 KB Output is correct
9 Correct 241 ms 269960 KB Output is correct
10 Correct 268 ms 273008 KB Output is correct
11 Correct 242 ms 272820 KB Output is correct
12 Correct 243 ms 273860 KB Output is correct
13 Runtime error 453 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 182 ms 258756 KB Output is correct
2 Correct 200 ms 256756 KB Output is correct
3 Correct 174 ms 256612 KB Output is correct
4 Correct 191 ms 256596 KB Output is correct
5 Correct 173 ms 256848 KB Output is correct
6 Correct 205 ms 256704 KB Output is correct
7 Correct 190 ms 256816 KB Output is correct
8 Correct 185 ms 256888 KB Output is correct
9 Correct 187 ms 257360 KB Output is correct
10 Correct 241 ms 269960 KB Output is correct
11 Correct 268 ms 273008 KB Output is correct
12 Correct 242 ms 272820 KB Output is correct
13 Correct 243 ms 273860 KB Output is correct
14 Runtime error 453 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -