UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212704#3829. CPanjunnan067ms8188kbC++111.4kb2024-10-20 09:49:562024-10-20 12:38:31

answer

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int from, to, weight;
};

vector<vector<int>> adj;
vector<Edge> edges;
int n;

int findRoot(int x, vector<int>& parent) {
    if (parent[x] == x) return x;
    return findRoot(parent[x], parent);
}

void unionSets(int x, int y, vector<int>& parent) {
    int rootX = findRoot(x, parent);
    int rootY = findRoot(y, parent);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

int kruskalMST() {
    vector<int> parent(n + 1);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    int mstCost = 0;
    for (const auto& edge : edges) {
        int x = edge.from, y = edge.to;
        if (findRoot(x, parent) != findRoot(y, parent)) {
            unionSets(x, y, parent);
            mstCost += edge.weight;
        }
    }

    return mstCost;
}

int main() {
    cin >> n;
    adj.resize(n + 1);
    edges.resize(n - 1);

    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
        edges[i] = {x, y, 1};
    }

    int minCost = kruskalMST();
    cout << minCost << endl;

    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 1252kb

input:

5
3 1
1 5
2 4
5 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1252kb

input:

5
5 1
1 4
4 2
2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: -10
Wrong Answer
time: 0ms
memory: 1248kb

input:

5
4 5
4 3
4 1
4 2

output:

4

result:

wrong answer 1st numbers differ - expected: '6', found: '4'

Subtask #2:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 1256kb

input:

100
63 38
17 33
44 12
9 66
21 98
2 49
68 67
75 42
78 25
92 6
67 17
90 19
48 51
83 9
20 94
68 4
64 58...

output:

99

result:

wrong answer 1st numbers differ - expected: '167', found: '99'

Subtask #3:

score: 0
Wrong Answer

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 1324kb

input:

1000
228 978
939 994
911 13
8 806
680 958
779 832
673 924
627 806
354 476
320 218
766 848
171 944
90...

output:

999

result:

wrong answer 1st numbers differ - expected: '1893', found: '999'

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 67ms
memory: 8188kb

input:

100000
44881 88880
79640 18741
56510 31493
27649 50461
7015 98523
26337 91384
17594 52397
37312 3409...

output:

99999

result:

wrong answer 1st numbers differ - expected: '199052', found: '99999'

Subtask #5:

score: 0
Time Limit Exceeded

Test #22:

score: 0
Time Limit Exceeded

input:

1000000
198444 939986
569807 470692
847908 557044
739959 80274
772656 222835
832266 382872
267873 10...

output:


result: