oj.uz

Submission #516351

# Submission time Handle Problem Language Result Execution time Memory
516351 2022-01-21T07:53:31 Z Jomnoi Sightseeing (NOI14_sightseeing) C++17
25 / 25
 2431 ms 200676 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12168 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15224 KB Output is correct
2 Correct 30 ms 14740 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 123608 KB Output is correct
2 Correct 2431 ms 200676 KB Output is correct