oj.uz

Submission #972913

# Submission time Handle Problem Language Result Execution time Memory
972913 2024-05-01T10:13:12 Z DAleksa Swapping Cities (APIO20_swap) C++17
6 / 100
 284 ms 59988 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;
        sz[v] += sz[u];
        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 = 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; j >= 0; j--) {
//        cout << up[u][j] << "\n";
        if(up[u][j] == -1) continue;
        if(is_ancestor(up[u][j], v)) continue;
        u = up[u][j];
//        cout << u << " " << j << "\n";
    }
    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;
        for(int j = 0; j <= LOG; j++) up[i][j] = -1;
    }
    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]];
                dsu.id[par] = tsz;
                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 i = 0; i <= root; i++) {
//        for(int j = 0; j <= 5; j++) cout << up[i][j] << " ";
//        cout << "\n";
//    }
    for(int j = 1; j <= LOG; j++) {
        for(int i = 0; i <= root; i++) {
            if(up[i][j - 1] == -1) up[i][j] = -1;
            else up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
//    cout << "TU: " << LCA(4, 5) << "\n";
}

int getMinimumFuelCapacity(int X, int Y) {
//    return -1;
    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


6 7
0 1 1
1 2 2
0 2 3
3 4 4
4 5 5
3 5 6
2 3 7
15
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37724 KB Output is correct
2 Correct 23 ms 37724 KB Output is correct
3 Correct 19 ms 37920 KB Output is correct
4 Correct 22 ms 37724 KB Output is correct
5 Correct 27 ms 37724 KB Output is correct
6 Correct 23 ms 37808 KB Output is correct
7 Correct 22 ms 37980 KB Output is correct
8 Correct 20 ms 37820 KB Output is correct
9 Correct 78 ms 42792 KB Output is correct
10 Correct 74 ms 43976 KB Output is correct
11 Correct 79 ms 44004 KB Output is correct
12 Correct 83 ms 44216 KB Output is correct
13 Correct 63 ms 41248 KB Output is correct
14 Correct 69 ms 43196 KB Output is correct
15 Correct 126 ms 46124 KB Output is correct
16 Correct 122 ms 45716 KB Output is correct
17 Correct 119 ms 46056 KB Output is correct
18 Correct 115 ms 43136 KB Output is correct
19 Correct 88 ms 42292 KB Output is correct
20 Correct 154 ms 52168 KB Output is correct
21 Correct 147 ms 52344 KB Output is correct
22 Correct 147 ms 52888 KB Output is correct
23 Correct 124 ms 50056 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37724 KB Output is correct
2 Correct 23 ms 37724 KB Output is correct
3 Incorrect 284 ms 59988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37724 KB Output is correct
2 Correct 23 ms 37724 KB Output is correct
3 Correct 19 ms 37920 KB Output is correct
4 Correct 22 ms 37724 KB Output is correct
5 Correct 27 ms 37724 KB Output is correct
6 Correct 23 ms 37808 KB Output is correct
7 Correct 22 ms 37980 KB Output is correct
8 Correct 20 ms 37820 KB Output is correct
9 Correct 24 ms 37720 KB Output is correct
10 Correct 22 ms 37844 KB Output is correct
11 Incorrect 21 ms 37820 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37720 KB Output is correct
2 Correct 19 ms 37724 KB Output is correct
3 Correct 23 ms 37724 KB Output is correct
4 Correct 19 ms 37920 KB Output is correct
5 Correct 22 ms 37724 KB Output is correct
6 Correct 27 ms 37724 KB Output is correct
7 Correct 23 ms 37808 KB Output is correct
8 Correct 22 ms 37980 KB Output is correct
9 Correct 20 ms 37820 KB Output is correct
10 Correct 78 ms 42792 KB Output is correct
11 Correct 74 ms 43976 KB Output is correct
12 Correct 79 ms 44004 KB Output is correct
13 Correct 83 ms 44216 KB Output is correct
14 Correct 63 ms 41248 KB Output is correct
15 Correct 22 ms 37844 KB Output is correct
16 Incorrect 21 ms 37820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37724 KB Output is correct
2 Correct 23 ms 37724 KB Output is correct
3 Correct 19 ms 37920 KB Output is correct
4 Correct 22 ms 37724 KB Output is correct
5 Correct 27 ms 37724 KB Output is correct
6 Correct 23 ms 37808 KB Output is correct
7 Correct 22 ms 37980 KB Output is correct
8 Correct 20 ms 37820 KB Output is correct
9 Correct 78 ms 42792 KB Output is correct
10 Correct 74 ms 43976 KB Output is correct
11 Correct 79 ms 44004 KB Output is correct
12 Correct 83 ms 44216 KB Output is correct
13 Correct 63 ms 41248 KB Output is correct
14 Correct 69 ms 43196 KB Output is correct
15 Correct 126 ms 46124 KB Output is correct
16 Correct 122 ms 45716 KB Output is correct
17 Correct 119 ms 46056 KB Output is correct
18 Correct 115 ms 43136 KB Output is correct
19 Incorrect 284 ms 59988 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37720 KB Output is correct
2 Correct 19 ms 37724 KB Output is correct
3 Correct 23 ms 37724 KB Output is correct
4 Correct 19 ms 37920 KB Output is correct
5 Correct 22 ms 37724 KB Output is correct
6 Correct 27 ms 37724 KB Output is correct
7 Correct 23 ms 37808 KB Output is correct
8 Correct 22 ms 37980 KB Output is correct
9 Correct 20 ms 37820 KB Output is correct
10 Correct 78 ms 42792 KB Output is correct
11 Correct 74 ms 43976 KB Output is correct
12 Correct 79 ms 44004 KB Output is correct
13 Correct 83 ms 44216 KB Output is correct
14 Correct 63 ms 41248 KB Output is correct
15 Correct 69 ms 43196 KB Output is correct
16 Correct 126 ms 46124 KB Output is correct
17 Correct 122 ms 45716 KB Output is correct
18 Correct 119 ms 46056 KB Output is correct
19 Correct 115 ms 43136 KB Output is correct
20 Incorrect 284 ms 59988 KB Output isn't correct
21 Halted 0 ms 0 KB -