oj.uz

Submission #655143

# Submission time Handle Problem Language Result Execution time Memory
655143 2022-11-03T09:13:22 Z dooompy Swapping Cities (APIO20_swap) C++17
0 / 100
 4 ms 8532 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;

    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 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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