oj.uz

Submission #972921

# Submission time Handle Problem Language Result Execution time Memory
972921 2024-05-01T10:17:27 Z DAleksa Swapping Cities (APIO20_swap) C++17
13 / 100
 439 ms 353956 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; 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 200 ms 334928 KB Output is correct
2 Correct 196 ms 334664 KB Output is correct
3 Correct 196 ms 334660 KB Output is correct
4 Correct 197 ms 334716 KB Output is correct
5 Correct 199 ms 334672 KB Output is correct
6 Correct 197 ms 334772 KB Output is correct
7 Correct 223 ms 334784 KB Output is correct
8 Correct 196 ms 334676 KB Output is correct
9 Correct 239 ms 340040 KB Output is correct
10 Correct 255 ms 341300 KB Output is correct
11 Correct 258 ms 341012 KB Output is correct
12 Correct 251 ms 341360 KB Output is correct
13 Correct 239 ms 338712 KB Output is correct
14 Correct 245 ms 340416 KB Output is correct
15 Correct 300 ms 343636 KB Output is correct
16 Correct 294 ms 343140 KB Output is correct
17 Correct 308 ms 343344 KB Output is correct
18 Correct 283 ms 340352 KB Output is correct
19 Correct 245 ms 339444 KB Output is correct
20 Correct 310 ms 345076 KB Output is correct
21 Correct 305 ms 345384 KB Output is correct
22 Correct 316 ms 345932 KB Output is correct
23 Correct 303 ms 342912 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 334928 KB Output is correct
2 Correct 196 ms 334664 KB Output is correct
3 Correct 439 ms 352244 KB Output is correct
4 Correct 427 ms 353956 KB Output is correct
5 Correct 402 ms 353740 KB Output is correct
6 Correct 405 ms 352408 KB Output is correct
7 Correct 419 ms 352448 KB Output is correct
8 Correct 402 ms 353124 KB Output is correct
9 Correct 405 ms 352380 KB Output is correct
10 Correct 386 ms 351720 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 334928 KB Output is correct
2 Correct 196 ms 334664 KB Output is correct
3 Correct 196 ms 334660 KB Output is correct
4 Correct 197 ms 334716 KB Output is correct
5 Correct 199 ms 334672 KB Output is correct
6 Correct 197 ms 334772 KB Output is correct
7 Correct 223 ms 334784 KB Output is correct
8 Correct 196 ms 334676 KB Output is correct
9 Correct 206 ms 334800 KB Output is correct
10 Correct 198 ms 334672 KB Output is correct
11 Incorrect 201 ms 334684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 334800 KB Output is correct
2 Correct 200 ms 334928 KB Output is correct
3 Correct 196 ms 334664 KB Output is correct
4 Correct 196 ms 334660 KB Output is correct
5 Correct 197 ms 334716 KB Output is correct
6 Correct 199 ms 334672 KB Output is correct
7 Correct 197 ms 334772 KB Output is correct
8 Correct 223 ms 334784 KB Output is correct
9 Correct 196 ms 334676 KB Output is correct
10 Correct 239 ms 340040 KB Output is correct
11 Correct 255 ms 341300 KB Output is correct
12 Correct 258 ms 341012 KB Output is correct
13 Correct 251 ms 341360 KB Output is correct
14 Correct 239 ms 338712 KB Output is correct
15 Correct 198 ms 334672 KB Output is correct
16 Incorrect 201 ms 334684 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 334928 KB Output is correct
2 Correct 196 ms 334664 KB Output is correct
3 Correct 196 ms 334660 KB Output is correct
4 Correct 197 ms 334716 KB Output is correct
5 Correct 199 ms 334672 KB Output is correct
6 Correct 197 ms 334772 KB Output is correct
7 Correct 223 ms 334784 KB Output is correct
8 Correct 196 ms 334676 KB Output is correct
9 Correct 239 ms 340040 KB Output is correct
10 Correct 255 ms 341300 KB Output is correct
11 Correct 258 ms 341012 KB Output is correct
12 Correct 251 ms 341360 KB Output is correct
13 Correct 239 ms 338712 KB Output is correct
14 Correct 245 ms 340416 KB Output is correct
15 Correct 300 ms 343636 KB Output is correct
16 Correct 294 ms 343140 KB Output is correct
17 Correct 308 ms 343344 KB Output is correct
18 Correct 283 ms 340352 KB Output is correct
19 Correct 439 ms 352244 KB Output is correct
20 Correct 427 ms 353956 KB Output is correct
21 Correct 402 ms 353740 KB Output is correct
22 Correct 405 ms 352408 KB Output is correct
23 Correct 419 ms 352448 KB Output is correct
24 Correct 402 ms 353124 KB Output is correct
25 Correct 405 ms 352380 KB Output is correct
26 Correct 386 ms 351720 KB Output is correct
27 Correct 198 ms 334672 KB Output is correct
28 Incorrect 201 ms 334684 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 334800 KB Output is correct
2 Correct 200 ms 334928 KB Output is correct
3 Correct 196 ms 334664 KB Output is correct
4 Correct 196 ms 334660 KB Output is correct
5 Correct 197 ms 334716 KB Output is correct
6 Correct 199 ms 334672 KB Output is correct
7 Correct 197 ms 334772 KB Output is correct
8 Correct 223 ms 334784 KB Output is correct
9 Correct 196 ms 334676 KB Output is correct
10 Correct 239 ms 340040 KB Output is correct
11 Correct 255 ms 341300 KB Output is correct
12 Correct 258 ms 341012 KB Output is correct
13 Correct 251 ms 341360 KB Output is correct
14 Correct 239 ms 338712 KB Output is correct
15 Correct 245 ms 340416 KB Output is correct
16 Correct 300 ms 343636 KB Output is correct
17 Correct 294 ms 343140 KB Output is correct
18 Correct 308 ms 343344 KB Output is correct
19 Correct 283 ms 340352 KB Output is correct
20 Correct 439 ms 352244 KB Output is correct
21 Correct 427 ms 353956 KB Output is correct
22 Correct 402 ms 353740 KB Output is correct
23 Correct 405 ms 352408 KB Output is correct
24 Correct 419 ms 352448 KB Output is correct
25 Correct 402 ms 353124 KB Output is correct
26 Correct 405 ms 352380 KB Output is correct
27 Correct 386 ms 351720 KB Output is correct
28 Correct 198 ms 334672 KB Output is correct
29 Incorrect 201 ms 334684 KB Output isn't correct
30 Halted 0 ms 0 KB -