oj.uz

Submission #655144

# Submission time Handle Problem Language Result Execution time Memory
655144 2022-11-03T09:14:06 Z dooompy Swapping Cities (APIO20_swap) C++17
0 / 100
 371 ms 39768 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

int par[300005];
int cost[300005];
int deg[100005];
int up[300005][20];
int depth[300005];

vector<int> adj[300005];
int id;

int findset(int i) {
    return (par[i] == i ? i : par[i] = findset(par[i]));
}

void onion(int a, int b, int idx) {
    par[a] = idx, par[b] = idx;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    vector<pair<int, pair<int, int>>> edges;
    fill(cost, cost+300005, INT_MAX);

    for (int i = 0; i < M; i++) {
        edges.push_back({W[i], {U[i] + 1, V[i] + 1}});
    }

    id = N;
    
    for (int i = 1; i <= 300004; i++) par[i] = i;

    sort(edges.begin(), edges.end());

    for (auto [c, edge] : edges) {
        int a = findset(edge.first), b = findset(edge.second);

        if (a == b) {
            cost[a] = min(cost[a], c);
        } else {
            id++;

            onion(a, b, id);

            adj[id].push_back(a); adj[id].push_back(b);
            up[a][0] = id; up[b][0] = id;

            if (cost[a] != INT_MAX || cost[b] != INT_MAX || deg[edge.first] >= 3 || deg[edge.second] >= 3) {
                cost[id] = min(cost[id], c);
            }
        }

        deg[edge.first]++; deg[edge.second]++;
    }

    for (int i = id; i >= 1; i--) {
        if (depth[i] == 0) depth[i] = 1;

        for (auto nxt : adj[i]) {
            depth[nxt] = depth[i] + 1;
            cost[nxt] = min(cost[nxt], cost[i]);
        }
    }

    for (int i = id; i >= 1; i--) {
        for (int j = 1; j < 20; j++) up[i][j] = up[up[i][j-1]][j-1];
    }

}

int getMinimumFuelCapacity(int X, int Y) {

    if (depth[X] > depth[Y]) swap(X, Y);

    for (int i = 19; ~i; i--) {
        if (depth[up[Y][i]] >= depth[X]) Y = up[Y][i];
    }

    for (int i = 19; ~i; i--) {
        if (up[X][i] != up[Y][i]) {
            X = up[X][i];
            Y = up[Y][i];
        }
    }

    int lca = up[X][0];

    return (cost[lca] == INT_MAX ? -1 : cost[lca]);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9656 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9928 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9936 KB Output is correct
9 Correct 74 ms 29692 KB Output is correct
10 Correct 117 ms 34240 KB Output is correct
11 Correct 90 ms 33800 KB Output is correct
12 Correct 100 ms 35248 KB Output is correct
13 Correct 124 ms 35852 KB Output is correct
14 Correct 86 ms 30104 KB Output is correct
15 Correct 248 ms 38452 KB Output is correct
16 Correct 238 ms 37516 KB Output is correct
17 Correct 239 ms 39112 KB Output is correct
18 Correct 371 ms 39768 KB Output is correct
19 Incorrect 96 ms 18640 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9656 KB Output is correct
3 Incorrect 317 ms 37640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9656 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9928 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9936 KB Output is correct
9 Incorrect 5 ms 9664 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9656 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9928 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9936 KB Output is correct
9 Correct 74 ms 29692 KB Output is correct
10 Correct 117 ms 34240 KB Output is correct
11 Correct 90 ms 33800 KB Output is correct
12 Correct 100 ms 35248 KB Output is correct
13 Correct 124 ms 35852 KB Output is correct
14 Correct 86 ms 30104 KB Output is correct
15 Correct 248 ms 38452 KB Output is correct
16 Correct 238 ms 37516 KB Output is correct
17 Correct 239 ms 39112 KB Output is correct
18 Correct 371 ms 39768 KB Output is correct
19 Incorrect 317 ms 37640 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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