oj.uz

Submission #972918

# Submission time Handle Problem Language Result Execution time Memory
972918 2024-05-01T10:16:08 Z DAleksa Swapping Cities (APIO20_swap) C++17
13 / 100
 455 ms 353128 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 204 ms 334672 KB Output is correct
2 Correct 203 ms 334672 KB Output is correct
3 Correct 200 ms 334676 KB Output is correct
4 Correct 199 ms 334672 KB Output is correct
5 Correct 204 ms 334680 KB Output is correct
6 Correct 214 ms 334672 KB Output is correct
7 Correct 201 ms 334672 KB Output is correct
8 Correct 201 ms 334604 KB Output is correct
9 Correct 241 ms 340040 KB Output is correct
10 Correct 256 ms 341144 KB Output is correct
11 Correct 260 ms 341128 KB Output is correct
12 Correct 255 ms 341336 KB Output is correct
13 Correct 241 ms 338604 KB Output is correct
14 Correct 251 ms 340384 KB Output is correct
15 Correct 299 ms 343204 KB Output is correct
16 Correct 289 ms 342988 KB Output is correct
17 Correct 292 ms 342228 KB Output is correct
18 Correct 288 ms 339068 KB Output is correct
19 Correct 247 ms 338392 KB Output is correct
20 Correct 306 ms 343204 KB Output is correct
21 Correct 307 ms 344248 KB Output is correct
22 Correct 311 ms 345704 KB Output is correct
23 Correct 318 ms 341636 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 334672 KB Output is correct
2 Correct 203 ms 334672 KB Output is correct
3 Correct 401 ms 351972 KB Output is correct
4 Correct 403 ms 350780 KB Output is correct
5 Correct 407 ms 350484 KB Output is correct
6 Correct 443 ms 350632 KB Output is correct
7 Correct 451 ms 349656 KB Output is correct
8 Correct 437 ms 349948 KB Output is correct
9 Correct 455 ms 353128 KB Output is correct
10 Correct 406 ms 351740 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 334672 KB Output is correct
2 Correct 203 ms 334672 KB Output is correct
3 Correct 200 ms 334676 KB Output is correct
4 Correct 199 ms 334672 KB Output is correct
5 Correct 204 ms 334680 KB Output is correct
6 Correct 214 ms 334672 KB Output is correct
7 Correct 201 ms 334672 KB Output is correct
8 Correct 201 ms 334604 KB Output is correct
9 Correct 214 ms 333332 KB Output is correct
10 Correct 199 ms 334676 KB Output is correct
11 Incorrect 200 ms 334648 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 333332 KB Output is correct
2 Correct 204 ms 334672 KB Output is correct
3 Correct 203 ms 334672 KB Output is correct
4 Correct 200 ms 334676 KB Output is correct
5 Correct 199 ms 334672 KB Output is correct
6 Correct 204 ms 334680 KB Output is correct
7 Correct 214 ms 334672 KB Output is correct
8 Correct 201 ms 334672 KB Output is correct
9 Correct 201 ms 334604 KB Output is correct
10 Correct 241 ms 340040 KB Output is correct
11 Correct 256 ms 341144 KB Output is correct
12 Correct 260 ms 341128 KB Output is correct
13 Correct 255 ms 341336 KB Output is correct
14 Correct 241 ms 338604 KB Output is correct
15 Correct 199 ms 334676 KB Output is correct
16 Incorrect 200 ms 334648 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 334672 KB Output is correct
2 Correct 203 ms 334672 KB Output is correct
3 Correct 200 ms 334676 KB Output is correct
4 Correct 199 ms 334672 KB Output is correct
5 Correct 204 ms 334680 KB Output is correct
6 Correct 214 ms 334672 KB Output is correct
7 Correct 201 ms 334672 KB Output is correct
8 Correct 201 ms 334604 KB Output is correct
9 Correct 241 ms 340040 KB Output is correct
10 Correct 256 ms 341144 KB Output is correct
11 Correct 260 ms 341128 KB Output is correct
12 Correct 255 ms 341336 KB Output is correct
13 Correct 241 ms 338604 KB Output is correct
14 Correct 251 ms 340384 KB Output is correct
15 Correct 299 ms 343204 KB Output is correct
16 Correct 289 ms 342988 KB Output is correct
17 Correct 292 ms 342228 KB Output is correct
18 Correct 288 ms 339068 KB Output is correct
19 Correct 401 ms 351972 KB Output is correct
20 Correct 403 ms 350780 KB Output is correct
21 Correct 407 ms 350484 KB Output is correct
22 Correct 443 ms 350632 KB Output is correct
23 Correct 451 ms 349656 KB Output is correct
24 Correct 437 ms 349948 KB Output is correct
25 Correct 455 ms 353128 KB Output is correct
26 Correct 406 ms 351740 KB Output is correct
27 Correct 199 ms 334676 KB Output is correct
28 Incorrect 200 ms 334648 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 333332 KB Output is correct
2 Correct 204 ms 334672 KB Output is correct
3 Correct 203 ms 334672 KB Output is correct
4 Correct 200 ms 334676 KB Output is correct
5 Correct 199 ms 334672 KB Output is correct
6 Correct 204 ms 334680 KB Output is correct
7 Correct 214 ms 334672 KB Output is correct
8 Correct 201 ms 334672 KB Output is correct
9 Correct 201 ms 334604 KB Output is correct
10 Correct 241 ms 340040 KB Output is correct
11 Correct 256 ms 341144 KB Output is correct
12 Correct 260 ms 341128 KB Output is correct
13 Correct 255 ms 341336 KB Output is correct
14 Correct 241 ms 338604 KB Output is correct
15 Correct 251 ms 340384 KB Output is correct
16 Correct 299 ms 343204 KB Output is correct
17 Correct 289 ms 342988 KB Output is correct
18 Correct 292 ms 342228 KB Output is correct
19 Correct 288 ms 339068 KB Output is correct
20 Correct 401 ms 351972 KB Output is correct
21 Correct 403 ms 350780 KB Output is correct
22 Correct 407 ms 350484 KB Output is correct
23 Correct 443 ms 350632 KB Output is correct
24 Correct 451 ms 349656 KB Output is correct
25 Correct 437 ms 349948 KB Output is correct
26 Correct 455 ms 353128 KB Output is correct
27 Correct 406 ms 351740 KB Output is correct
28 Correct 199 ms 334676 KB Output is correct
29 Incorrect 200 ms 334648 KB Output isn't correct
30 Halted 0 ms 0 KB -