oj.uz

Submission #1043821

# Submission time Handle Problem Language Result Execution time Memory
1043821 2024-08-04T19:49:34 Z VMaksimoski008 Swapping Cities (APIO20_swap) C++17
13 / 100
 146 ms 50988 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;
const int LOG = 20;

int par[maxn+5], C[maxn+5], deg[maxn+5], dp[maxn+5], P[maxn+5], ok[maxn+5], G[maxn+5], d[maxn+5], n, m, N, up[maxn+5][LOG];
vector<int> graph[maxn+5];
vector<array<int, 3> > edges;

int find(int u) {
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

void uni(int a, int b) {
    a = find(a); b = find(b); n++;
    if(a == b) C[n] = 1;
    par[n] = par[a] = par[b] = n;
    // if(G[a] || G[b]) G[n] = 1;
    // if(C[a] || C[b]) C[n] = 1;
    graph[n].push_back(a);
    if(a != b) graph[n].push_back(b);
}

void dfs(int u, int last) {
    for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
    if(ok[u]) last = u;
    dp[u] = last;

    for(int &v : graph[u]) {
        d[v] = d[u] + 1;
        up[v][0] = u;
        P[v] = u;
        dfs(v, last);
    }
}

int get_lca(int a, int b) {
    if(d[a] < d[b]) swap(a, b);
    int D = d[a] - d[b];
    for(int j=LOG-1; j>=0; j--)
        if(D & (1 << j)) a = up[a][j];

    if(a == b) return a;

    for(int j=LOG-1; j>=0; j--)
        if(up[a][j] != up[b][j]) a = up[a][j], b = up[b][j];
    return up[a][0];
}

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    n = _N;
    N = _N;
    m = _M;

    for(int i=1; i<=_N+_M; i++) {
        par[i] = i;
        C[i] = deg[i] = G[i] = 0;
    }

    for(int i=0; i<m; i++) edges.push_back({ W[i], U[i] + 1, V[i] + 1});
    sort(edges.begin(), edges.end());
    for(auto &[w, u, v] : edges) {
        deg[u]++; deg[v]++;
        if(deg[u] >= 3) G[n+1] = 1;
        if(deg[v] >= 3) G[n+1] = 1;
        uni(u, v);
    }

    for(int i=1; i<=n; i++) ok[i] = (G[i] || C[i]);
    dfs(n, -1);
}

int getMinimumFuelCapacity(int X, int Y) {
    int lca = get_lca(X+1, Y+1);
    if(dp[lca] == -1) return -1;
    return edges[dp[lca]-N-1][0];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19084 KB Output is correct
3 Correct 2 ms 19032 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 2 ms 19100 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 2 ms 19036 KB Output is correct
9 Correct 40 ms 35392 KB Output is correct
10 Correct 53 ms 39368 KB Output is correct
11 Correct 55 ms 39104 KB Output is correct
12 Correct 63 ms 40392 KB Output is correct
13 Correct 57 ms 44108 KB Output is correct
14 Correct 51 ms 35536 KB Output is correct
15 Correct 113 ms 41296 KB Output is correct
16 Correct 95 ms 40776 KB Output is correct
17 Correct 100 ms 42028 KB Output is correct
18 Correct 146 ms 45960 KB Output is correct
19 Correct 45 ms 24708 KB Output is correct
20 Correct 98 ms 42568 KB Output is correct
21 Correct 100 ms 41896 KB Output is correct
22 Correct 114 ms 43560 KB Output is correct
23 Correct 130 ms 47404 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19084 KB Output is correct
3 Correct 105 ms 49592 KB Output is correct
4 Correct 105 ms 50988 KB Output is correct
5 Correct 110 ms 50264 KB Output is correct
6 Correct 105 ms 50736 KB Output is correct
7 Correct 107 ms 50500 KB Output is correct
8 Correct 105 ms 49268 KB Output is correct
9 Correct 117 ms 50244 KB Output is correct
10 Correct 111 ms 49028 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Correct 2 ms 19084 KB Output is correct
4 Correct 2 ms 19032 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 2 ms 19100 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 2 ms 19036 KB Output is correct
9 Correct 2 ms 19036 KB Output is correct
10 Correct 40 ms 35392 KB Output is correct
11 Correct 53 ms 39368 KB Output is correct
12 Correct 55 ms 39104 KB Output is correct
13 Correct 63 ms 40392 KB Output is correct
14 Correct 57 ms 44108 KB Output is correct
15 Correct 3 ms 19036 KB Output is correct
16 Incorrect 2 ms 19036 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19084 KB Output is correct
3 Correct 2 ms 19032 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 2 ms 19100 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 2 ms 19036 KB Output is correct
9 Correct 40 ms 35392 KB Output is correct
10 Correct 53 ms 39368 KB Output is correct
11 Correct 55 ms 39104 KB Output is correct
12 Correct 63 ms 40392 KB Output is correct
13 Correct 57 ms 44108 KB Output is correct
14 Correct 51 ms 35536 KB Output is correct
15 Correct 113 ms 41296 KB Output is correct
16 Correct 95 ms 40776 KB Output is correct
17 Correct 100 ms 42028 KB Output is correct
18 Correct 146 ms 45960 KB Output is correct
19 Correct 105 ms 49592 KB Output is correct
20 Correct 105 ms 50988 KB Output is correct
21 Correct 110 ms 50264 KB Output is correct
22 Correct 105 ms 50736 KB Output is correct
23 Correct 107 ms 50500 KB Output is correct
24 Correct 105 ms 49268 KB Output is correct
25 Correct 117 ms 50244 KB Output is correct
26 Correct 111 ms 49028 KB Output is correct
27 Correct 3 ms 19036 KB Output is correct
28 Incorrect 2 ms 19036 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Correct 2 ms 19084 KB Output is correct
4 Correct 2 ms 19032 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 2 ms 19100 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 2 ms 19036 KB Output is correct
9 Correct 2 ms 19036 KB Output is correct
10 Correct 40 ms 35392 KB Output is correct
11 Correct 53 ms 39368 KB Output is correct
12 Correct 55 ms 39104 KB Output is correct
13 Correct 63 ms 40392 KB Output is correct
14 Correct 57 ms 44108 KB Output is correct
15 Correct 51 ms 35536 KB Output is correct
16 Correct 113 ms 41296 KB Output is correct
17 Correct 95 ms 40776 KB Output is correct
18 Correct 100 ms 42028 KB Output is correct
19 Correct 146 ms 45960 KB Output is correct
20 Correct 105 ms 49592 KB Output is correct
21 Correct 105 ms 50988 KB Output is correct
22 Correct 110 ms 50264 KB Output is correct
23 Correct 105 ms 50736 KB Output is correct
24 Correct 107 ms 50500 KB Output is correct
25 Correct 105 ms 49268 KB Output is correct
26 Correct 117 ms 50244 KB Output is correct
27 Correct 111 ms 49028 KB Output is correct
28 Correct 3 ms 19036 KB Output is correct
29 Incorrect 2 ms 19036 KB Output isn't correct
30 Halted 0 ms 0 KB -