oj.uz

Submission #972924

# Submission time Handle Problem Language Result Execution time Memory
972924 2024-05-01T10:24:29 Z DAleksa Swapping Cities (APIO20_swap) C++17
13 / 100
 518 ms 515368 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 + 5e5, 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 346 ms 496976 KB Output is correct
2 Correct 272 ms 496976 KB Output is correct
3 Correct 278 ms 496980 KB Output is correct
4 Correct 307 ms 496960 KB Output is correct
5 Correct 325 ms 497196 KB Output is correct
6 Correct 306 ms 497052 KB Output is correct
7 Correct 297 ms 497036 KB Output is correct
8 Correct 298 ms 496956 KB Output is correct
9 Correct 343 ms 502852 KB Output is correct
10 Correct 361 ms 503888 KB Output is correct
11 Correct 363 ms 503704 KB Output is correct
12 Correct 364 ms 504096 KB Output is correct
13 Correct 318 ms 501376 KB Output is correct
14 Correct 353 ms 503024 KB Output is correct
15 Correct 402 ms 505840 KB Output is correct
16 Correct 395 ms 505856 KB Output is correct
17 Correct 405 ms 506160 KB Output is correct
18 Correct 387 ms 503168 KB Output is correct
19 Correct 350 ms 501844 KB Output is correct
20 Correct 415 ms 507776 KB Output is correct
21 Correct 411 ms 508116 KB Output is correct
22 Correct 419 ms 508592 KB Output is correct
23 Correct 379 ms 505944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 496976 KB Output is correct
2 Correct 272 ms 496976 KB Output is correct
3 Correct 471 ms 514660 KB Output is correct
4 Correct 513 ms 515368 KB Output is correct
5 Correct 518 ms 515040 KB Output is correct
6 Correct 483 ms 515188 KB Output is correct
7 Correct 484 ms 515152 KB Output is correct
8 Correct 482 ms 514720 KB Output is correct
9 Correct 507 ms 515140 KB Output is correct
10 Correct 509 ms 514420 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 496976 KB Output is correct
2 Correct 272 ms 496976 KB Output is correct
3 Correct 278 ms 496980 KB Output is correct
4 Correct 307 ms 496960 KB Output is correct
5 Correct 325 ms 497196 KB Output is correct
6 Correct 306 ms 497052 KB Output is correct
7 Correct 297 ms 497036 KB Output is correct
8 Correct 298 ms 496956 KB Output is correct
9 Correct 283 ms 497440 KB Output is correct
10 Correct 296 ms 497040 KB Output is correct
11 Incorrect 309 ms 497064 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 497440 KB Output is correct
2 Correct 346 ms 496976 KB Output is correct
3 Correct 272 ms 496976 KB Output is correct
4 Correct 278 ms 496980 KB Output is correct
5 Correct 307 ms 496960 KB Output is correct
6 Correct 325 ms 497196 KB Output is correct
7 Correct 306 ms 497052 KB Output is correct
8 Correct 297 ms 497036 KB Output is correct
9 Correct 298 ms 496956 KB Output is correct
10 Correct 343 ms 502852 KB Output is correct
11 Correct 361 ms 503888 KB Output is correct
12 Correct 363 ms 503704 KB Output is correct
13 Correct 364 ms 504096 KB Output is correct
14 Correct 318 ms 501376 KB Output is correct
15 Correct 296 ms 497040 KB Output is correct
16 Incorrect 309 ms 497064 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 496976 KB Output is correct
2 Correct 272 ms 496976 KB Output is correct
3 Correct 278 ms 496980 KB Output is correct
4 Correct 307 ms 496960 KB Output is correct
5 Correct 325 ms 497196 KB Output is correct
6 Correct 306 ms 497052 KB Output is correct
7 Correct 297 ms 497036 KB Output is correct
8 Correct 298 ms 496956 KB Output is correct
9 Correct 343 ms 502852 KB Output is correct
10 Correct 361 ms 503888 KB Output is correct
11 Correct 363 ms 503704 KB Output is correct
12 Correct 364 ms 504096 KB Output is correct
13 Correct 318 ms 501376 KB Output is correct
14 Correct 353 ms 503024 KB Output is correct
15 Correct 402 ms 505840 KB Output is correct
16 Correct 395 ms 505856 KB Output is correct
17 Correct 405 ms 506160 KB Output is correct
18 Correct 387 ms 503168 KB Output is correct
19 Correct 471 ms 514660 KB Output is correct
20 Correct 513 ms 515368 KB Output is correct
21 Correct 518 ms 515040 KB Output is correct
22 Correct 483 ms 515188 KB Output is correct
23 Correct 484 ms 515152 KB Output is correct
24 Correct 482 ms 514720 KB Output is correct
25 Correct 507 ms 515140 KB Output is correct
26 Correct 509 ms 514420 KB Output is correct
27 Correct 296 ms 497040 KB Output is correct
28 Incorrect 309 ms 497064 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 497440 KB Output is correct
2 Correct 346 ms 496976 KB Output is correct
3 Correct 272 ms 496976 KB Output is correct
4 Correct 278 ms 496980 KB Output is correct
5 Correct 307 ms 496960 KB Output is correct
6 Correct 325 ms 497196 KB Output is correct
7 Correct 306 ms 497052 KB Output is correct
8 Correct 297 ms 497036 KB Output is correct
9 Correct 298 ms 496956 KB Output is correct
10 Correct 343 ms 502852 KB Output is correct
11 Correct 361 ms 503888 KB Output is correct
12 Correct 363 ms 503704 KB Output is correct
13 Correct 364 ms 504096 KB Output is correct
14 Correct 318 ms 501376 KB Output is correct
15 Correct 353 ms 503024 KB Output is correct
16 Correct 402 ms 505840 KB Output is correct
17 Correct 395 ms 505856 KB Output is correct
18 Correct 405 ms 506160 KB Output is correct
19 Correct 387 ms 503168 KB Output is correct
20 Correct 471 ms 514660 KB Output is correct
21 Correct 513 ms 515368 KB Output is correct
22 Correct 518 ms 515040 KB Output is correct
23 Correct 483 ms 515188 KB Output is correct
24 Correct 484 ms 515152 KB Output is correct
25 Correct 482 ms 514720 KB Output is correct
26 Correct 507 ms 515140 KB Output is correct
27 Correct 509 ms 514420 KB Output is correct
28 Correct 296 ms 497040 KB Output is correct
29 Incorrect 309 ms 497064 KB Output isn't correct
30 Halted 0 ms 0 KB -