oj.uz

Submission #972905

# Submission time Handle Problem Language Result Execution time Memory
972905 2024-05-01T10:10:45 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 243 ms 59340 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 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37720 KB Output is correct
2 Correct 20 ms 37724 KB Output is correct
3 Correct 23 ms 37720 KB Output is correct
4 Correct 21 ms 37980 KB Output is correct
5 Correct 22 ms 37824 KB Output is correct
6 Correct 22 ms 37980 KB Output is correct
7 Correct 22 ms 37980 KB Output is correct
8 Correct 26 ms 37876 KB Output is correct
9 Correct 70 ms 44564 KB Output is correct
10 Correct 73 ms 45944 KB Output is correct
11 Correct 78 ms 45656 KB Output is correct
12 Correct 82 ms 46192 KB Output is correct
13 Correct 70 ms 43384 KB Output is correct
14 Correct 67 ms 44968 KB Output is correct
15 Correct 115 ms 50264 KB Output is correct
16 Correct 118 ms 50340 KB Output is correct
17 Correct 116 ms 50516 KB Output is correct
18 Correct 105 ms 47484 KB Output is correct
19 Incorrect 68 ms 43600 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37720 KB Output is correct
2 Correct 20 ms 37724 KB Output is correct
3 Incorrect 243 ms 59340 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 37720 KB Output is correct
2 Correct 20 ms 37724 KB Output is correct
3 Correct 23 ms 37720 KB Output is correct
4 Correct 21 ms 37980 KB Output is correct
5 Correct 22 ms 37824 KB Output is correct
6 Correct 22 ms 37980 KB Output is correct
7 Correct 22 ms 37980 KB Output is correct
8 Correct 26 ms 37876 KB Output is correct
9 Incorrect 20 ms 37724 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 37724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37720 KB Output is correct
2 Correct 20 ms 37724 KB Output is correct
3 Correct 23 ms 37720 KB Output is correct
4 Correct 21 ms 37980 KB Output is correct
5 Correct 22 ms 37824 KB Output is correct
6 Correct 22 ms 37980 KB Output is correct
7 Correct 22 ms 37980 KB Output is correct
8 Correct 26 ms 37876 KB Output is correct
9 Correct 70 ms 44564 KB Output is correct
10 Correct 73 ms 45944 KB Output is correct
11 Correct 78 ms 45656 KB Output is correct
12 Correct 82 ms 46192 KB Output is correct
13 Correct 70 ms 43384 KB Output is correct
14 Correct 67 ms 44968 KB Output is correct
15 Correct 115 ms 50264 KB Output is correct
16 Correct 118 ms 50340 KB Output is correct
17 Correct 116 ms 50516 KB Output is correct
18 Correct 105 ms 47484 KB Output is correct
19 Incorrect 243 ms 59340 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 37724 KB Output isn't correct
2 Halted 0 ms 0 KB -