oj.uz

Submission #972915

# Submission time Handle Problem Language Result Execution time Memory
972915 2024-05-01T10:13:52 Z DAleksa Swapping Cities (APIO20_swap) C++17
6 / 100
 274 ms 59736 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 18 ms 37724 KB Output is correct
2 Correct 21 ms 37724 KB Output is correct
3 Correct 19 ms 37724 KB Output is correct
4 Correct 23 ms 38012 KB Output is correct
5 Correct 24 ms 37724 KB Output is correct
6 Correct 21 ms 37980 KB Output is correct
7 Correct 22 ms 37720 KB Output is correct
8 Correct 25 ms 37964 KB Output is correct
9 Correct 77 ms 42820 KB Output is correct
10 Correct 75 ms 43980 KB Output is correct
11 Correct 80 ms 43568 KB Output is correct
12 Correct 75 ms 44136 KB Output is correct
13 Correct 73 ms 41308 KB Output is correct
14 Correct 76 ms 43076 KB Output is correct
15 Correct 114 ms 45908 KB Output is correct
16 Correct 125 ms 45724 KB Output is correct
17 Correct 113 ms 46108 KB Output is correct
18 Correct 101 ms 43136 KB Output is correct
19 Correct 68 ms 42328 KB Output is correct
20 Correct 146 ms 47796 KB Output is correct
21 Correct 128 ms 48172 KB Output is correct
22 Correct 136 ms 48560 KB Output is correct
23 Correct 126 ms 45700 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37724 KB Output is correct
2 Correct 21 ms 37724 KB Output is correct
3 Incorrect 274 ms 59736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37724 KB Output is correct
2 Correct 21 ms 37724 KB Output is correct
3 Correct 19 ms 37724 KB Output is correct
4 Correct 23 ms 38012 KB Output is correct
5 Correct 24 ms 37724 KB Output is correct
6 Correct 21 ms 37980 KB Output is correct
7 Correct 22 ms 37720 KB Output is correct
8 Correct 25 ms 37964 KB Output is correct
9 Correct 20 ms 37872 KB Output is correct
10 Correct 22 ms 37976 KB Output is correct
11 Incorrect 21 ms 37976 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37872 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37724 KB Output is correct
4 Correct 19 ms 37724 KB Output is correct
5 Correct 23 ms 38012 KB Output is correct
6 Correct 24 ms 37724 KB Output is correct
7 Correct 21 ms 37980 KB Output is correct
8 Correct 22 ms 37720 KB Output is correct
9 Correct 25 ms 37964 KB Output is correct
10 Correct 77 ms 42820 KB Output is correct
11 Correct 75 ms 43980 KB Output is correct
12 Correct 80 ms 43568 KB Output is correct
13 Correct 75 ms 44136 KB Output is correct
14 Correct 73 ms 41308 KB Output is correct
15 Correct 22 ms 37976 KB Output is correct
16 Incorrect 21 ms 37976 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37724 KB Output is correct
2 Correct 21 ms 37724 KB Output is correct
3 Correct 19 ms 37724 KB Output is correct
4 Correct 23 ms 38012 KB Output is correct
5 Correct 24 ms 37724 KB Output is correct
6 Correct 21 ms 37980 KB Output is correct
7 Correct 22 ms 37720 KB Output is correct
8 Correct 25 ms 37964 KB Output is correct
9 Correct 77 ms 42820 KB Output is correct
10 Correct 75 ms 43980 KB Output is correct
11 Correct 80 ms 43568 KB Output is correct
12 Correct 75 ms 44136 KB Output is correct
13 Correct 73 ms 41308 KB Output is correct
14 Correct 76 ms 43076 KB Output is correct
15 Correct 114 ms 45908 KB Output is correct
16 Correct 125 ms 45724 KB Output is correct
17 Correct 113 ms 46108 KB Output is correct
18 Correct 101 ms 43136 KB Output is correct
19 Incorrect 274 ms 59736 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37872 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37724 KB Output is correct
4 Correct 19 ms 37724 KB Output is correct
5 Correct 23 ms 38012 KB Output is correct
6 Correct 24 ms 37724 KB Output is correct
7 Correct 21 ms 37980 KB Output is correct
8 Correct 22 ms 37720 KB Output is correct
9 Correct 25 ms 37964 KB Output is correct
10 Correct 77 ms 42820 KB Output is correct
11 Correct 75 ms 43980 KB Output is correct
12 Correct 80 ms 43568 KB Output is correct
13 Correct 75 ms 44136 KB Output is correct
14 Correct 73 ms 41308 KB Output is correct
15 Correct 76 ms 43076 KB Output is correct
16 Correct 114 ms 45908 KB Output is correct
17 Correct 125 ms 45724 KB Output is correct
18 Correct 113 ms 46108 KB Output is correct
19 Correct 101 ms 43136 KB Output is correct
20 Incorrect 274 ms 59736 KB Output isn't correct
21 Halted 0 ms 0 KB -