oj.uz

Submission #1106500

# Submission time Handle Problem Language Result Execution time Memory
1106500 2024-10-30T13:31:18 Z vladilius Swapping Cities (APIO20_swap) C++17
13 / 100
 215 ms 49296 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int inf = 3e5;
const int infv = numeric_limits<int> :: max();

struct dsu{
    vector<int> p, d, A;
    vector<vector<int>> g;
    vector<bool> f;
    int n, cc, k;
    void init(int ns){
        n = ns;
        d.resize(n + 1);
        p.resize(inf + 1);
        f.resize(inf + 1);
        for (int i = 1; i <= inf; i++){
            p[i] = i;
        }
        cc = n;
        g.resize(inf + 1);
        A.assign(inf + 1, infv);
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y, int w){
        int a = get(x), b = get(y);
        if (a == b){
            if (!f[a]){
                cc++;
                p[a] = cc;
                A[cc] = w;
                g[cc].pb(a);
            }
            return;
        }
        
        if (f[a] || f[b] || d[x] == 2 || d[y] == 2){
            cc++;
            p[a] = p[b] = cc;
            A[cc] = w;
            g[cc].pb(a);
            g[cc].pb(b);
            f[b] = 1;
        }
        else {
            cc++;
            p[a] = p[b] = cc;
            g[cc].pb(a);
            g[cc].pb(b);
            d[x]++; d[y]++;
        }
    }
    vector<int> tin, tout, out;
    vector<vector<int>> pw;
    int lg, timer;
    void fill(int v, int pr){
        tin[v] = ++timer;
        out[v] = min(out[pr], A[v]);
        pw[v][0] = pr;
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (int i: g[v]){
            fill(i, v);
        }
        tout[v] = timer;
    }
    void build(){
        tin.resize(cc + 1);
        tout.resize(cc + 1);
        lg = log2(cc);
        pw.resize(cc + 1);
        for (int i = 1; i <= cc; i++){
            pw[i].resize(lg + 1);
        }
        timer = 0;
        out.assign(inf + 1, infv);
        fill(cc, cc);
        
        for (int i = 1; i <= inf; i++){
            if (out[i] == infv){
                out[i] = -1;
            }
        }
    }
    bool check(int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    }
    int lca(int x, int y){
        for (int i = lg; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    }
    int get(int x, int y){
        return out[lca(x, y)];
    }
};

dsu T;
int n, m;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
    n = N; m = M;
    vector<arr3> ed;
    for (int i = 0; i < m; i++){
        ed.pb({W[i], U[i] + 1, V[i] + 1});
    }
    sort(ed.begin(), ed.end());
    T.init(n);
    for (auto [f, x, y]: ed){
        T.unite(x, y, f);
    }
    T.build();
}

int getMinimumFuelCapacity(int x, int y){
    x++; y++;
    return T.get(x, y);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10832 KB Output is correct
2 Correct 5 ms 10832 KB Output is correct
3 Correct 5 ms 10832 KB Output is correct
4 Correct 5 ms 11088 KB Output is correct
5 Correct 6 ms 11260 KB Output is correct
6 Correct 5 ms 11088 KB Output is correct
7 Correct 5 ms 11088 KB Output is correct
8 Correct 6 ms 11088 KB Output is correct
9 Correct 89 ms 35260 KB Output is correct
10 Correct 101 ms 40804 KB Output is correct
11 Correct 91 ms 40380 KB Output is correct
12 Correct 104 ms 41892 KB Output is correct
13 Correct 121 ms 43964 KB Output is correct
14 Correct 85 ms 35524 KB Output is correct
15 Correct 151 ms 44836 KB Output is correct
16 Correct 151 ms 43976 KB Output is correct
17 Correct 151 ms 45756 KB Output is correct
18 Correct 215 ms 47688 KB Output is correct
19 Correct 60 ms 20812 KB Output is correct
20 Correct 144 ms 45088 KB Output is correct
21 Correct 160 ms 44340 KB Output is correct
22 Correct 162 ms 46208 KB Output is correct
23 Correct 200 ms 48384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10832 KB Output is correct
2 Correct 5 ms 10832 KB Output is correct
3 Correct 172 ms 47628 KB Output is correct
4 Correct 169 ms 49296 KB Output is correct
5 Correct 169 ms 48364 KB Output is correct
6 Correct 174 ms 49044 KB Output is correct
7 Correct 170 ms 48892 KB Output is correct
8 Correct 172 ms 47404 KB Output is correct
9 Correct 198 ms 48580 KB Output is correct
10 Correct 192 ms 47220 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10832 KB Output is correct
2 Correct 5 ms 10832 KB Output is correct
3 Correct 5 ms 10832 KB Output is correct
4 Correct 5 ms 11088 KB Output is correct
5 Correct 6 ms 11260 KB Output is correct
6 Correct 5 ms 11088 KB Output is correct
7 Correct 5 ms 11088 KB Output is correct
8 Correct 6 ms 11088 KB Output is correct
9 Correct 5 ms 10832 KB Output is correct
10 Correct 6 ms 11088 KB Output is correct
11 Incorrect 5 ms 11088 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10832 KB Output is correct
2 Correct 5 ms 10832 KB Output is correct
3 Correct 5 ms 10832 KB Output is correct
4 Correct 5 ms 10832 KB Output is correct
5 Correct 5 ms 11088 KB Output is correct
6 Correct 6 ms 11260 KB Output is correct
7 Correct 5 ms 11088 KB Output is correct
8 Correct 5 ms 11088 KB Output is correct
9 Correct 6 ms 11088 KB Output is correct
10 Correct 89 ms 35260 KB Output is correct
11 Correct 101 ms 40804 KB Output is correct
12 Correct 91 ms 40380 KB Output is correct
13 Correct 104 ms 41892 KB Output is correct
14 Correct 121 ms 43964 KB Output is correct
15 Correct 6 ms 11088 KB Output is correct
16 Incorrect 5 ms 11088 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10832 KB Output is correct
2 Correct 5 ms 10832 KB Output is correct
3 Correct 5 ms 10832 KB Output is correct
4 Correct 5 ms 11088 KB Output is correct
5 Correct 6 ms 11260 KB Output is correct
6 Correct 5 ms 11088 KB Output is correct
7 Correct 5 ms 11088 KB Output is correct
8 Correct 6 ms 11088 KB Output is correct
9 Correct 89 ms 35260 KB Output is correct
10 Correct 101 ms 40804 KB Output is correct
11 Correct 91 ms 40380 KB Output is correct
12 Correct 104 ms 41892 KB Output is correct
13 Correct 121 ms 43964 KB Output is correct
14 Correct 85 ms 35524 KB Output is correct
15 Correct 151 ms 44836 KB Output is correct
16 Correct 151 ms 43976 KB Output is correct
17 Correct 151 ms 45756 KB Output is correct
18 Correct 215 ms 47688 KB Output is correct
19 Correct 172 ms 47628 KB Output is correct
20 Correct 169 ms 49296 KB Output is correct
21 Correct 169 ms 48364 KB Output is correct
22 Correct 174 ms 49044 KB Output is correct
23 Correct 170 ms 48892 KB Output is correct
24 Correct 172 ms 47404 KB Output is correct
25 Correct 198 ms 48580 KB Output is correct
26 Correct 192 ms 47220 KB Output is correct
27 Correct 6 ms 11088 KB Output is correct
28 Incorrect 5 ms 11088 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10832 KB Output is correct
2 Correct 5 ms 10832 KB Output is correct
3 Correct 5 ms 10832 KB Output is correct
4 Correct 5 ms 10832 KB Output is correct
5 Correct 5 ms 11088 KB Output is correct
6 Correct 6 ms 11260 KB Output is correct
7 Correct 5 ms 11088 KB Output is correct
8 Correct 5 ms 11088 KB Output is correct
9 Correct 6 ms 11088 KB Output is correct
10 Correct 89 ms 35260 KB Output is correct
11 Correct 101 ms 40804 KB Output is correct
12 Correct 91 ms 40380 KB Output is correct
13 Correct 104 ms 41892 KB Output is correct
14 Correct 121 ms 43964 KB Output is correct
15 Correct 85 ms 35524 KB Output is correct
16 Correct 151 ms 44836 KB Output is correct
17 Correct 151 ms 43976 KB Output is correct
18 Correct 151 ms 45756 KB Output is correct
19 Correct 215 ms 47688 KB Output is correct
20 Correct 172 ms 47628 KB Output is correct
21 Correct 169 ms 49296 KB Output is correct
22 Correct 169 ms 48364 KB Output is correct
23 Correct 174 ms 49044 KB Output is correct
24 Correct 170 ms 48892 KB Output is correct
25 Correct 172 ms 47404 KB Output is correct
26 Correct 198 ms 48580 KB Output is correct
27 Correct 192 ms 47220 KB Output is correct
28 Correct 6 ms 11088 KB Output is correct
29 Incorrect 5 ms 11088 KB Output isn't correct
30 Halted 0 ms 0 KB -