Submission #389811

#	Time	Username	Problem	Language	Result	Execution time	Memory
389811		sumit_kk10	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	2637 ms	211132 KiB

sightseeing

#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 (stderr)

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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10