답안 #655145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
655145	2022-11-03T09:15:00 Z	dooompy	자매 도시 (APIO20_swap)	C++17	6 / 100	391 ms	40116 KB

swap

#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) {
    X++; 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
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	6 ms	9776 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	9940 KB	Output is correct
6	Correct	5 ms	9812 KB	Output is correct
7	Correct	5 ms	9940 KB	Output is correct
8	Correct	6 ms	9940 KB	Output is correct
9	Correct	73 ms	28108 KB	Output is correct
10	Correct	94 ms	32192 KB	Output is correct
11	Correct	115 ms	31880 KB	Output is correct
12	Correct	122 ms	33088 KB	Output is correct
13	Correct	112 ms	33696 KB	Output is correct
14	Correct	91 ms	28236 KB	Output is correct
15	Correct	263 ms	33952 KB	Output is correct
16	Correct	242 ms	33296 KB	Output is correct
17	Correct	250 ms	34756 KB	Output is correct
18	Correct	391 ms	35292 KB	Output is correct
19	Correct	102 ms	16608 KB	Output is correct
20	Correct	307 ms	38484 KB	Output is correct
21	Correct	217 ms	37932 KB	Output is correct
22	Correct	249 ms	39584 KB	Output is correct
23	Correct	332 ms	40116 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	6 ms	9776 KB	Output is correct
3	Correct	362 ms	33744 KB	Output is correct
4	Correct	342 ms	38632 KB	Output is correct
5	Correct	379 ms	38244 KB	Output is correct
6	Correct	348 ms	38476 KB	Output is correct
7	Incorrect	317 ms	38584 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	6 ms	9776 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	9940 KB	Output is correct
6	Correct	5 ms	9812 KB	Output is correct
7	Correct	5 ms	9940 KB	Output is correct
8	Correct	6 ms	9940 KB	Output is correct
9	Correct	6 ms	9684 KB	Output is correct
10	Correct	5 ms	9940 KB	Output is correct
11	Incorrect	6 ms	9940 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	6 ms	9776 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9812 KB	Output is correct
6	Correct	6 ms	9940 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	5 ms	9940 KB	Output is correct
9	Correct	6 ms	9940 KB	Output is correct
10	Correct	73 ms	28108 KB	Output is correct
11	Correct	94 ms	32192 KB	Output is correct
12	Correct	115 ms	31880 KB	Output is correct
13	Correct	122 ms	33088 KB	Output is correct
14	Correct	112 ms	33696 KB	Output is correct
15	Correct	5 ms	9940 KB	Output is correct
16	Incorrect	6 ms	9940 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	6 ms	9776 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	9940 KB	Output is correct
6	Correct	5 ms	9812 KB	Output is correct
7	Correct	5 ms	9940 KB	Output is correct
8	Correct	6 ms	9940 KB	Output is correct
9	Correct	73 ms	28108 KB	Output is correct
10	Correct	94 ms	32192 KB	Output is correct
11	Correct	115 ms	31880 KB	Output is correct
12	Correct	122 ms	33088 KB	Output is correct
13	Correct	112 ms	33696 KB	Output is correct
14	Correct	91 ms	28236 KB	Output is correct
15	Correct	263 ms	33952 KB	Output is correct
16	Correct	242 ms	33296 KB	Output is correct
17	Correct	250 ms	34756 KB	Output is correct
18	Correct	391 ms	35292 KB	Output is correct
19	Correct	362 ms	33744 KB	Output is correct
20	Correct	342 ms	38632 KB	Output is correct
21	Correct	379 ms	38244 KB	Output is correct
22	Correct	348 ms	38476 KB	Output is correct
23	Incorrect	317 ms	38584 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	6 ms	9776 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9812 KB	Output is correct
6	Correct	6 ms	9940 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	5 ms	9940 KB	Output is correct
9	Correct	6 ms	9940 KB	Output is correct
10	Correct	73 ms	28108 KB	Output is correct
11	Correct	94 ms	32192 KB	Output is correct
12	Correct	115 ms	31880 KB	Output is correct
13	Correct	122 ms	33088 KB	Output is correct
14	Correct	112 ms	33696 KB	Output is correct
15	Correct	91 ms	28236 KB	Output is correct
16	Correct	263 ms	33952 KB	Output is correct
17	Correct	242 ms	33296 KB	Output is correct
18	Correct	250 ms	34756 KB	Output is correct
19	Correct	391 ms	35292 KB	Output is correct
20	Correct	362 ms	33744 KB	Output is correct
21	Correct	342 ms	38632 KB	Output is correct
22	Correct	379 ms	38244 KB	Output is correct
23	Correct	348 ms	38476 KB	Output is correct
24	Incorrect	317 ms	38584 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

답안 #655145

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0