oj.uz

Submission #968867

# Submission time Handle Problem Language Result Execution time Memory
968867 2024-04-24T08:07:28 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 60 ms 4232 KB 
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
const int MAX_N=2e5+5,INF=1e9+7;
int parent[MAX_N];
int find_root(int u){
    if(parent[u]==u) return u;
    return parent[u] = find_root(parent[u]);
}
bool try_merge(int u,int v){
    int root_u= find_root(u);
    int root_v = find_root(v);
    if(root_u!=root_v){
        parent[root_u]=root_v;
        return true;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,m,u,v,w;
    int tmp,tmp2;
    cin >> n >> tmp >> m;
    for(int i=0;i<tmp;++i) cin >> tmp2;
    vector<pair<int,pair<int,int>>> vec;
    for(int i=0;i<m;++i){
        cin >> u >> v >> w;
        vec.push_back({w, {u, v}});
    }
    for(int i=0;i<=n;++i) parent[i]=i;
    sort(vec.begin(),vec.end());
    long long cnt=0,idx=0,sum=0;
    while(cnt<n-1 && idx<m){
        u = vec[idx].second.first,v=vec[idx].second.second;
        w = vec[idx].first;
        if(try_merge(u,v)){
            cnt++;
            sum += w;
        }
        idx++;
    }
    cout << sum;
    return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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