oj.uz

Submission #389811

# Submission time Handle Problem Language Result Execution time Memory
389811 2021-04-14T14:42:26 Z sumit_kk10 Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2637 ms 211132 KB 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
vector<pair<int, pair<int, int> > > edges;
int n, m, q, component[N], ans[N];
vector<pair<int, int> > tree[N];
bool vis[N];

int find(int x){
    while(true){
        if(x == component[x])
            return x;
        component[x] = component[component[x]];
        x = component[x];
    }
}

void merge(int a, int b){
    int u = find(a), v = find(b);
    component[u] = v;
}

void MST(){
    for(int i = 0; i < edges.size(); ++i){
        int u = edges[i].second.first, v = edges[i].second.second;
        int c = edges[i].first;
        if(find(u) == find(v)) continue;
        tree[u].push_back({v, c});
        tree[v].push_back({u, c});
        merge(u, v);
    }
}

void dfs(int source, int mn){
    ans[source] = mn;
    vis[source] = 1;
    for(auto k : tree[source])
        if(!vis[k.first])
            dfs(k.first, min(mn, k.second));
}

int main(){
    fast;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++i)
        component[i] = i;
    for(int i = 1; i <= m; ++i){
        int u, v, c;
        cin >> u >> v >> c;
        edges.push_back({c, {u, v}});
    }
    sort(edges.rbegin(), edges.rend());
    MST();
    dfs(1, INT_MAX);
    ans[1] = 0;
    while(q--){
        int node;
        cin >> node;
        cout << ans[node] << '\n';
    }
    return 0;
}

Compilation message

sightseeing.cpp: In function 'void MST()':
sightseeing.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < edges.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23728 KB Output is correct
2 Correct 16 ms 23824 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23852 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 25968 KB Output is correct
2 Correct 41 ms 25848 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1860 ms 78968 KB Output is correct
2 Correct 2637 ms 211132 KB Output is correct