oj.uz

Submission #1043816

# Submission time Handle Problem Language Result Execution time Memory
1043816 2024-08-04T19:36:06 Z VMaksimoski008 Swapping Cities (APIO20_swap) C++17
0 / 100
 130 ms 48060 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);
}

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 16984 KB Output is correct
2 Correct 2 ms 16984 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 4 ms 16996 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 53 ms 33836 KB Output is correct
10 Correct 57 ms 37740 KB Output is correct
11 Correct 54 ms 37316 KB Output is correct
12 Correct 74 ms 38800 KB Output is correct
13 Correct 58 ms 42696 KB Output is correct
14 Correct 53 ms 33944 KB Output is correct
15 Correct 99 ms 39756 KB Output is correct
16 Correct 115 ms 39188 KB Output is correct
17 Correct 111 ms 40540 KB Output is correct
18 Correct 130 ms 44336 KB Output is correct
19 Incorrect 43 ms 21656 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 2 ms 16984 KB Output is correct
3 Incorrect 113 ms 48060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 2 ms 16984 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 4 ms 16996 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Incorrect 2 ms 16988 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 2 ms 16984 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 4 ms 16996 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 53 ms 33836 KB Output is correct
10 Correct 57 ms 37740 KB Output is correct
11 Correct 54 ms 37316 KB Output is correct
12 Correct 74 ms 38800 KB Output is correct
13 Correct 58 ms 42696 KB Output is correct
14 Correct 53 ms 33944 KB Output is correct
15 Correct 99 ms 39756 KB Output is correct
16 Correct 115 ms 39188 KB Output is correct
17 Correct 111 ms 40540 KB Output is correct
18 Correct 130 ms 44336 KB Output is correct
19 Incorrect 113 ms 48060 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 16988 KB Output isn't correct
2 Halted 0 ms 0 KB -