Submission #516351

#	Time	Username	Problem	Language	Result	Execution time	Memory
516351		Jomnoi	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	2431 ms	200676 KiB

sightseeing

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 5e5 + 10;
const int INF = 1e9 + 7;

vector <pair <int, int>> adj[N];
int parent[N];
int weight[N];
int ans[N];

int root(int u) {
    if(u == parent[u]) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

void dfs(int u, int p) {
    for(auto [v, w] : adj[u]) {
        if(v == p) {
            continue;
        }

        ans[v] = min(ans[u], w);
        dfs(v, u);
    }
}

int main() {
    int n, m, q;
    scanf(" %d %d %d", &n, &m, &q);
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    vector <tuple <int, int, int>> edge;
    while(m--) {
        int u, v, w;
        scanf(" %d %d %d", &u, &v, &w);
        edge.emplace_back(w, u, v);
    }
    sort(edge.rbegin(), edge.rend());

    for(auto [w, a, b] : edge) {
        int u = root(a), v = root(b);
        if(u == v) {
            continue;
        }

        if(u > v) {
            swap(u, v);
        }
        parent[v] = u;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }

    ans[1] = INF;
    dfs(1, -1);
    while(q--) {
        int x;
        scanf(" %d", &x);
        printf("%d\n", ans[x]);
    }
    return 0;
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf(" %d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf(" %d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf(" %d", &x);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10