oj.uz

Submission #972917

# Submission time Handle Problem Language Result Execution time Memory
972917 2024-05-01T10:15:12 Z DAleksa Swapping Cities (APIO20_swap) C++17
13 / 100
 341 ms 194628 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 = 5e5 + 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 95 ms 172668 KB Output is correct
2 Correct 92 ms 172648 KB Output is correct
3 Correct 90 ms 172628 KB Output is correct
4 Correct 101 ms 172760 KB Output is correct
5 Correct 90 ms 172672 KB Output is correct
6 Correct 136 ms 172636 KB Output is correct
7 Correct 108 ms 172660 KB Output is correct
8 Correct 105 ms 172768 KB Output is correct
9 Correct 135 ms 177476 KB Output is correct
10 Correct 158 ms 178488 KB Output is correct
11 Correct 149 ms 178144 KB Output is correct
12 Correct 162 ms 178648 KB Output is correct
13 Correct 135 ms 175904 KB Output is correct
14 Correct 139 ms 177612 KB Output is correct
15 Correct 191 ms 180468 KB Output is correct
16 Correct 215 ms 180216 KB Output is correct
17 Correct 189 ms 180484 KB Output is correct
18 Correct 173 ms 177632 KB Output is correct
19 Correct 140 ms 179172 KB Output is correct
20 Correct 201 ms 184276 KB Output is correct
21 Correct 205 ms 184656 KB Output is correct
22 Correct 213 ms 185140 KB Output is correct
23 Correct 192 ms 182092 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 172668 KB Output is correct
2 Correct 92 ms 172648 KB Output is correct
3 Correct 294 ms 190140 KB Output is correct
4 Correct 324 ms 194344 KB Output is correct
5 Correct 327 ms 194484 KB Output is correct
6 Correct 337 ms 194320 KB Output is correct
7 Correct 295 ms 194628 KB Output is correct
8 Correct 294 ms 193968 KB Output is correct
9 Correct 311 ms 194308 KB Output is correct
10 Correct 341 ms 193784 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 172668 KB Output is correct
2 Correct 92 ms 172648 KB Output is correct
3 Correct 90 ms 172628 KB Output is correct
4 Correct 101 ms 172760 KB Output is correct
5 Correct 90 ms 172672 KB Output is correct
6 Correct 136 ms 172636 KB Output is correct
7 Correct 108 ms 172660 KB Output is correct
8 Correct 105 ms 172768 KB Output is correct
9 Correct 107 ms 174704 KB Output is correct
10 Correct 94 ms 174860 KB Output is correct
11 Incorrect 91 ms 174680 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 174704 KB Output is correct
2 Correct 95 ms 172668 KB Output is correct
3 Correct 92 ms 172648 KB Output is correct
4 Correct 90 ms 172628 KB Output is correct
5 Correct 101 ms 172760 KB Output is correct
6 Correct 90 ms 172672 KB Output is correct
7 Correct 136 ms 172636 KB Output is correct
8 Correct 108 ms 172660 KB Output is correct
9 Correct 105 ms 172768 KB Output is correct
10 Correct 135 ms 177476 KB Output is correct
11 Correct 158 ms 178488 KB Output is correct
12 Correct 149 ms 178144 KB Output is correct
13 Correct 162 ms 178648 KB Output is correct
14 Correct 135 ms 175904 KB Output is correct
15 Correct 94 ms 174860 KB Output is correct
16 Incorrect 91 ms 174680 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 172668 KB Output is correct
2 Correct 92 ms 172648 KB Output is correct
3 Correct 90 ms 172628 KB Output is correct
4 Correct 101 ms 172760 KB Output is correct
5 Correct 90 ms 172672 KB Output is correct
6 Correct 136 ms 172636 KB Output is correct
7 Correct 108 ms 172660 KB Output is correct
8 Correct 105 ms 172768 KB Output is correct
9 Correct 135 ms 177476 KB Output is correct
10 Correct 158 ms 178488 KB Output is correct
11 Correct 149 ms 178144 KB Output is correct
12 Correct 162 ms 178648 KB Output is correct
13 Correct 135 ms 175904 KB Output is correct
14 Correct 139 ms 177612 KB Output is correct
15 Correct 191 ms 180468 KB Output is correct
16 Correct 215 ms 180216 KB Output is correct
17 Correct 189 ms 180484 KB Output is correct
18 Correct 173 ms 177632 KB Output is correct
19 Correct 294 ms 190140 KB Output is correct
20 Correct 324 ms 194344 KB Output is correct
21 Correct 327 ms 194484 KB Output is correct
22 Correct 337 ms 194320 KB Output is correct
23 Correct 295 ms 194628 KB Output is correct
24 Correct 294 ms 193968 KB Output is correct
25 Correct 311 ms 194308 KB Output is correct
26 Correct 341 ms 193784 KB Output is correct
27 Correct 94 ms 174860 KB Output is correct
28 Incorrect 91 ms 174680 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 174704 KB Output is correct
2 Correct 95 ms 172668 KB Output is correct
3 Correct 92 ms 172648 KB Output is correct
4 Correct 90 ms 172628 KB Output is correct
5 Correct 101 ms 172760 KB Output is correct
6 Correct 90 ms 172672 KB Output is correct
7 Correct 136 ms 172636 KB Output is correct
8 Correct 108 ms 172660 KB Output is correct
9 Correct 105 ms 172768 KB Output is correct
10 Correct 135 ms 177476 KB Output is correct
11 Correct 158 ms 178488 KB Output is correct
12 Correct 149 ms 178144 KB Output is correct
13 Correct 162 ms 178648 KB Output is correct
14 Correct 135 ms 175904 KB Output is correct
15 Correct 139 ms 177612 KB Output is correct
16 Correct 191 ms 180468 KB Output is correct
17 Correct 215 ms 180216 KB Output is correct
18 Correct 189 ms 180484 KB Output is correct
19 Correct 173 ms 177632 KB Output is correct
20 Correct 294 ms 190140 KB Output is correct
21 Correct 324 ms 194344 KB Output is correct
22 Correct 327 ms 194484 KB Output is correct
23 Correct 337 ms 194320 KB Output is correct
24 Correct 295 ms 194628 KB Output is correct
25 Correct 294 ms 193968 KB Output is correct
26 Correct 311 ms 194308 KB Output is correct
27 Correct 341 ms 193784 KB Output is correct
28 Correct 94 ms 174860 KB Output is correct
29 Incorrect 91 ms 174680 KB Output isn't correct
30 Halted 0 ms 0 KB -