oj.uz

Submission #972861

# Submission time Handle Problem Language Result Execution time Memory
972861 2024-05-01T09:12:22 Z DAleksa Swapping Cities (APIO20_swap) C++17
6 / 100
 420 ms 294356 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 = 1e6 + 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 - 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);
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 256588 KB Output is correct
2 Correct 179 ms 256596 KB Output is correct
3 Correct 180 ms 256656 KB Output is correct
4 Correct 179 ms 256592 KB Output is correct
5 Correct 192 ms 256852 KB Output is correct
6 Correct 178 ms 256852 KB Output is correct
7 Correct 193 ms 256812 KB Output is correct
8 Correct 182 ms 256704 KB Output is correct
9 Correct 226 ms 266568 KB Output is correct
10 Correct 246 ms 268876 KB Output is correct
11 Correct 231 ms 268616 KB Output is correct
12 Correct 235 ms 269516 KB Output is correct
13 Correct 254 ms 268884 KB Output is correct
14 Correct 233 ms 268692 KB Output is correct
15 Correct 283 ms 275316 KB Output is correct
16 Correct 282 ms 275000 KB Output is correct
17 Correct 287 ms 276016 KB Output is correct
18 Correct 271 ms 272772 KB Output is correct
19 Correct 247 ms 265300 KB Output is correct
20 Correct 300 ms 280776 KB Output is correct
21 Correct 294 ms 281348 KB Output is correct
22 Correct 298 ms 281776 KB Output is correct
23 Correct 298 ms 278912 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 256588 KB Output is correct
2 Correct 179 ms 256596 KB Output is correct
3 Incorrect 420 ms 294356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 256588 KB Output is correct
2 Correct 179 ms 256596 KB Output is correct
3 Correct 180 ms 256656 KB Output is correct
4 Correct 179 ms 256592 KB Output is correct
5 Correct 192 ms 256852 KB Output is correct
6 Correct 178 ms 256852 KB Output is correct
7 Correct 193 ms 256812 KB Output is correct
8 Correct 182 ms 256704 KB Output is correct
9 Correct 176 ms 258644 KB Output is correct
10 Incorrect 187 ms 258784 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 258644 KB Output is correct
2 Correct 199 ms 256588 KB Output is correct
3 Correct 179 ms 256596 KB Output is correct
4 Correct 180 ms 256656 KB Output is correct
5 Correct 179 ms 256592 KB Output is correct
6 Correct 192 ms 256852 KB Output is correct
7 Correct 178 ms 256852 KB Output is correct
8 Correct 193 ms 256812 KB Output is correct
9 Correct 182 ms 256704 KB Output is correct
10 Correct 226 ms 266568 KB Output is correct
11 Correct 246 ms 268876 KB Output is correct
12 Correct 231 ms 268616 KB Output is correct
13 Correct 235 ms 269516 KB Output is correct
14 Correct 254 ms 268884 KB Output is correct
15 Incorrect 187 ms 258784 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 256588 KB Output is correct
2 Correct 179 ms 256596 KB Output is correct
3 Correct 180 ms 256656 KB Output is correct
4 Correct 179 ms 256592 KB Output is correct
5 Correct 192 ms 256852 KB Output is correct
6 Correct 178 ms 256852 KB Output is correct
7 Correct 193 ms 256812 KB Output is correct
8 Correct 182 ms 256704 KB Output is correct
9 Correct 226 ms 266568 KB Output is correct
10 Correct 246 ms 268876 KB Output is correct
11 Correct 231 ms 268616 KB Output is correct
12 Correct 235 ms 269516 KB Output is correct
13 Correct 254 ms 268884 KB Output is correct
14 Correct 233 ms 268692 KB Output is correct
15 Correct 283 ms 275316 KB Output is correct
16 Correct 282 ms 275000 KB Output is correct
17 Correct 287 ms 276016 KB Output is correct
18 Correct 271 ms 272772 KB Output is correct
19 Incorrect 420 ms 294356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 258644 KB Output is correct
2 Correct 199 ms 256588 KB Output is correct
3 Correct 179 ms 256596 KB Output is correct
4 Correct 180 ms 256656 KB Output is correct
5 Correct 179 ms 256592 KB Output is correct
6 Correct 192 ms 256852 KB Output is correct
7 Correct 178 ms 256852 KB Output is correct
8 Correct 193 ms 256812 KB Output is correct
9 Correct 182 ms 256704 KB Output is correct
10 Correct 226 ms 266568 KB Output is correct
11 Correct 246 ms 268876 KB Output is correct
12 Correct 231 ms 268616 KB Output is correct
13 Correct 235 ms 269516 KB Output is correct
14 Correct 254 ms 268884 KB Output is correct
15 Correct 233 ms 268692 KB Output is correct
16 Correct 283 ms 275316 KB Output is correct
17 Correct 282 ms 275000 KB Output is correct
18 Correct 287 ms 276016 KB Output is correct
19 Correct 271 ms 272772 KB Output is correct
20 Incorrect 420 ms 294356 KB Output isn't correct
21 Halted 0 ms 0 KB -