oj.uz

Submission #972821

# Submission time Handle Problem Language Result Execution time Memory
972821 2024-05-01T08:29:43 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 575 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 = 1e5 + 10, LOG = 17;
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, 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


3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29276 KB Output is correct
2 Correct 18 ms 29392 KB Output is correct
3 Correct 19 ms 29544 KB Output is correct
4 Correct 19 ms 29276 KB Output is correct
5 Correct 21 ms 29272 KB Output is correct
6 Correct 20 ms 29276 KB Output is correct
7 Correct 24 ms 29532 KB Output is correct
8 Correct 21 ms 30024 KB Output is correct
9 Correct 68 ms 40144 KB Output is correct
10 Correct 97 ms 43188 KB Output is correct
11 Correct 75 ms 43096 KB Output is correct
12 Correct 82 ms 44160 KB Output is correct
13 Runtime error 575 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 18 ms 29276 KB Output is correct
2 Correct 18 ms 29392 KB Output is correct
3 Runtime error 568 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 18 ms 29276 KB Output is correct
2 Correct 18 ms 29392 KB Output is correct
3 Correct 19 ms 29544 KB Output is correct
4 Correct 19 ms 29276 KB Output is correct
5 Correct 21 ms 29272 KB Output is correct
6 Correct 20 ms 29276 KB Output is correct
7 Correct 24 ms 29532 KB Output is correct
8 Correct 21 ms 30024 KB Output is correct
9 Correct 19 ms 29272 KB Output is correct
10 Incorrect 20 ms 29532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29272 KB Output is correct
2 Correct 18 ms 29276 KB Output is correct
3 Correct 18 ms 29392 KB Output is correct
4 Correct 19 ms 29544 KB Output is correct
5 Correct 19 ms 29276 KB Output is correct
6 Correct 21 ms 29272 KB Output is correct
7 Correct 20 ms 29276 KB Output is correct
8 Correct 24 ms 29532 KB Output is correct
9 Correct 21 ms 30024 KB Output is correct
10 Correct 68 ms 40144 KB Output is correct
11 Correct 97 ms 43188 KB Output is correct
12 Correct 75 ms 43096 KB Output is correct
13 Correct 82 ms 44160 KB Output is correct
14 Runtime error 575 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 18 ms 29276 KB Output is correct
2 Correct 18 ms 29392 KB Output is correct
3 Correct 19 ms 29544 KB Output is correct
4 Correct 19 ms 29276 KB Output is correct
5 Correct 21 ms 29272 KB Output is correct
6 Correct 20 ms 29276 KB Output is correct
7 Correct 24 ms 29532 KB Output is correct
8 Correct 21 ms 30024 KB Output is correct
9 Correct 68 ms 40144 KB Output is correct
10 Correct 97 ms 43188 KB Output is correct
11 Correct 75 ms 43096 KB Output is correct
12 Correct 82 ms 44160 KB Output is correct
13 Runtime error 575 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 19 ms 29272 KB Output is correct
2 Correct 18 ms 29276 KB Output is correct
3 Correct 18 ms 29392 KB Output is correct
4 Correct 19 ms 29544 KB Output is correct
5 Correct 19 ms 29276 KB Output is correct
6 Correct 21 ms 29272 KB Output is correct
7 Correct 20 ms 29276 KB Output is correct
8 Correct 24 ms 29532 KB Output is correct
9 Correct 21 ms 30024 KB Output is correct
10 Correct 68 ms 40144 KB Output is correct
11 Correct 97 ms 43188 KB Output is correct
12 Correct 75 ms 43096 KB Output is correct
13 Correct 82 ms 44160 KB Output is correct
14 Runtime error 575 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -