oj.uz

답안 #655144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655144 2022-11-03T09:14:06 Z dooompy 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9664 KB Output isn't correct
2 Halted 0 ms 0 KB -