oj.uz

Submission #972854

# Submission time Handle Problem Language Result Execution time Memory
972854 2024-05-01T09:07:05 Z DAleksa Swapping Cities (APIO20_swap) C++17
0 / 100
 500 ms 524288 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;
        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) {
    vector<int> vec;
    for(int i : vec) {
        cout << i;
    }
    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 256596 KB Output is correct
2 Correct 194 ms 256592 KB Output is correct
3 Correct 177 ms 256596 KB Output is correct
4 Correct 176 ms 256592 KB Output is correct
5 Correct 172 ms 256852 KB Output is correct
6 Correct 183 ms 256852 KB Output is correct
7 Correct 211 ms 256644 KB Output is correct
8 Correct 175 ms 257504 KB Output is correct
9 Correct 225 ms 268716 KB Output is correct
10 Correct 237 ms 271724 KB Output is correct
11 Correct 237 ms 271568 KB Output is correct
12 Correct 241 ms 272584 KB Output is correct
13 Runtime error 500 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 256596 KB Output is correct
2 Correct 194 ms 256592 KB Output is correct
3 Runtime error 492 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 256596 KB Output is correct
2 Correct 194 ms 256592 KB Output is correct
3 Correct 177 ms 256596 KB Output is correct
4 Correct 176 ms 256592 KB Output is correct
5 Correct 172 ms 256852 KB Output is correct
6 Correct 183 ms 256852 KB Output is correct
7 Correct 211 ms 256644 KB Output is correct
8 Correct 175 ms 257504 KB Output is correct
9 Correct 173 ms 258768 KB Output is correct
10 Incorrect 173 ms 256852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 258768 KB Output is correct
2 Correct 228 ms 256596 KB Output is correct
3 Correct 194 ms 256592 KB Output is correct
4 Correct 177 ms 256596 KB Output is correct
5 Correct 176 ms 256592 KB Output is correct
6 Correct 172 ms 256852 KB Output is correct
7 Correct 183 ms 256852 KB Output is correct
8 Correct 211 ms 256644 KB Output is correct
9 Correct 175 ms 257504 KB Output is correct
10 Correct 225 ms 268716 KB Output is correct
11 Correct 237 ms 271724 KB Output is correct
12 Correct 237 ms 271568 KB Output is correct
13 Correct 241 ms 272584 KB Output is correct
14 Runtime error 500 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 256596 KB Output is correct
2 Correct 194 ms 256592 KB Output is correct
3 Correct 177 ms 256596 KB Output is correct
4 Correct 176 ms 256592 KB Output is correct
5 Correct 172 ms 256852 KB Output is correct
6 Correct 183 ms 256852 KB Output is correct
7 Correct 211 ms 256644 KB Output is correct
8 Correct 175 ms 257504 KB Output is correct
9 Correct 225 ms 268716 KB Output is correct
10 Correct 237 ms 271724 KB Output is correct
11 Correct 237 ms 271568 KB Output is correct
12 Correct 241 ms 272584 KB Output is correct
13 Runtime error 500 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 258768 KB Output is correct
2 Correct 228 ms 256596 KB Output is correct
3 Correct 194 ms 256592 KB Output is correct
4 Correct 177 ms 256596 KB Output is correct
5 Correct 176 ms 256592 KB Output is correct
6 Correct 172 ms 256852 KB Output is correct
7 Correct 183 ms 256852 KB Output is correct
8 Correct 211 ms 256644 KB Output is correct
9 Correct 175 ms 257504 KB Output is correct
10 Correct 225 ms 268716 KB Output is correct
11 Correct 237 ms 271724 KB Output is correct
12 Correct 237 ms 271568 KB Output is correct
13 Correct 241 ms 272584 KB Output is correct
14 Runtime error 500 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -