oj.uz

Submission #1043817

# Submission time Handle Problem Language Result Execution time Memory
1043817 2024-08-04T19:36:45 Z VMaksimoski008 Swapping Cities (APIO20_swap) C++17
7 / 100
 153 ms 49456 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

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

int par[maxn+5], cycle[maxn+5], deg[maxn+5], P[maxn+5], pref[maxn+5], good[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) cycle[n] = 1;
    par[n] = par[a] = par[b] = n;
    if(good[a] || good[b]) good[n] = 1;
    if(cycle[a] || cycle[b]) cycle[n] = 1;
    graph[n].push_back(a);
    if(a != b) graph[n].push_back(b);
}

void dfs(int u) {
    for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];

    for(int &v : graph[u]) {
        d[v] = d[u] + 1;
        up[v][0] = u;
        P[v] = u;
        pref[v] = pref[u] + (good[v] || cycle[v]);
        dfs(v);
    }
}

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;
        cycle[i] = deg[i] = good[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) good[n+1] = 1;
        if(deg[v] >= 3) good[n+1] = 1;
        uni(u, v);
    }

    dfs(n);
    pref[n] = (cycle[n] || good[n]);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++; Y++;
    int lca = get_lca(X, Y);
    if(!pref[lca]) return -1;
    
    while(true) {
        if(!lca) return -1;
        if(good[lca] || cycle[lca]) return edges[lca-N-1][0];
        lca = up[lca][0];
    }

    return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 17108 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 17000 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 44 ms 33824 KB Output is correct
10 Correct 73 ms 37732 KB Output is correct
11 Correct 71 ms 37316 KB Output is correct
12 Correct 62 ms 38868 KB Output is correct
13 Correct 56 ms 42696 KB Output is correct
14 Correct 48 ms 33888 KB Output is correct
15 Correct 100 ms 39688 KB Output is correct
16 Correct 98 ms 39180 KB Output is correct
17 Correct 122 ms 40440 KB Output is correct
18 Correct 153 ms 44480 KB Output is correct
19 Incorrect 52 ms 21496 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 110 ms 47808 KB Output is correct
4 Correct 114 ms 49456 KB Output is correct
5 Correct 111 ms 48656 KB Output is correct
6 Correct 110 ms 49216 KB Output is correct
7 Correct 112 ms 48928 KB Output is correct
8 Correct 108 ms 47732 KB Output is correct
9 Correct 106 ms 48744 KB Output is correct
10 Correct 111 ms 47488 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 17108 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 17000 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 2 ms 16988 KB Output is correct
12 Correct 2 ms 17016 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 2 ms 16988 KB Output is correct
15 Incorrect 2 ms 16988 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 17108 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 17000 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 44 ms 33824 KB Output is correct
11 Correct 73 ms 37732 KB Output is correct
12 Correct 71 ms 37316 KB Output is correct
13 Correct 62 ms 38868 KB Output is correct
14 Correct 56 ms 42696 KB Output is correct
15 Correct 2 ms 16988 KB Output is correct
16 Correct 2 ms 16988 KB Output is correct
17 Correct 2 ms 17016 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 2 ms 16988 KB Output is correct
20 Incorrect 2 ms 16988 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 17108 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 17000 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 44 ms 33824 KB Output is correct
10 Correct 73 ms 37732 KB Output is correct
11 Correct 71 ms 37316 KB Output is correct
12 Correct 62 ms 38868 KB Output is correct
13 Correct 56 ms 42696 KB Output is correct
14 Correct 48 ms 33888 KB Output is correct
15 Correct 100 ms 39688 KB Output is correct
16 Correct 98 ms 39180 KB Output is correct
17 Correct 122 ms 40440 KB Output is correct
18 Correct 153 ms 44480 KB Output is correct
19 Correct 110 ms 47808 KB Output is correct
20 Correct 114 ms 49456 KB Output is correct
21 Correct 111 ms 48656 KB Output is correct
22 Correct 110 ms 49216 KB Output is correct
23 Correct 112 ms 48928 KB Output is correct
24 Correct 108 ms 47732 KB Output is correct
25 Correct 106 ms 48744 KB Output is correct
26 Correct 111 ms 47488 KB Output is correct
27 Correct 2 ms 16988 KB Output is correct
28 Correct 2 ms 16988 KB Output is correct
29 Correct 2 ms 17016 KB Output is correct
30 Correct 3 ms 16988 KB Output is correct
31 Correct 2 ms 16988 KB Output is correct
32 Incorrect 2 ms 16988 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 17108 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 17000 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 44 ms 33824 KB Output is correct
11 Correct 73 ms 37732 KB Output is correct
12 Correct 71 ms 37316 KB Output is correct
13 Correct 62 ms 38868 KB Output is correct
14 Correct 56 ms 42696 KB Output is correct
15 Correct 48 ms 33888 KB Output is correct
16 Correct 100 ms 39688 KB Output is correct
17 Correct 98 ms 39180 KB Output is correct
18 Correct 122 ms 40440 KB Output is correct
19 Correct 153 ms 44480 KB Output is correct
20 Correct 110 ms 47808 KB Output is correct
21 Correct 114 ms 49456 KB Output is correct
22 Correct 111 ms 48656 KB Output is correct
23 Correct 110 ms 49216 KB Output is correct
24 Correct 112 ms 48928 KB Output is correct
25 Correct 108 ms 47732 KB Output is correct
26 Correct 106 ms 48744 KB Output is correct
27 Correct 111 ms 47488 KB Output is correct
28 Correct 2 ms 16988 KB Output is correct
29 Correct 2 ms 16988 KB Output is correct
30 Correct 2 ms 17016 KB Output is correct
31 Correct 3 ms 16988 KB Output is correct
32 Correct 2 ms 16988 KB Output is correct
33 Incorrect 2 ms 16988 KB Output isn't correct
34 Halted 0 ms 0 KB -