Submission #1355563

#TimeUsernameProblemLanguageResultExecution timeMemory
1355563michael12Sightseeing (NOI14_sightseeing)C++20
25 / 25
1151 ms119860 KiB
// #include "grader.h"
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<numeric>
#include<string>
#include<stack>
#include<queue>
#include<string.h>
#include<array>
#include<climits>
#include<algorithm>
#include<cmath>
using namespace std;
#define ff first
#define ss second
#define endl '\n'
const int maxn = 500005;
const int LG = 20;
static int up[maxn][LG];
static int mx[maxn][LG];
int depth[maxn];
int n, m;
vector<pair<int, int>> tree[maxn];
int ans[maxn];
void dfs(int u, int p, int mn) {
    ans[u] = mn;
    for (auto t : tree[u]) {
        if (t.ff == p) continue;
        dfs(t.ff, u, min(mn, t.ss));
    }
}
struct edges{
    int x, y, w, id;
};
int p[maxn], sz[maxn];
void make_set(int u){
    p[u] = u;
    sz[u] = 1LL;
}
int find(int x){
    if(x == p[x]) return x;
    return p[x] = find(p[x]);
}
void unite(int x, int z){
    int a = find(x);
    int b = find(z);
    if(a != b){
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
}
bool cmp(edges a, edges b){
    return a.w > b.w;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> m >> q;
    vector<edges> E(m);
    for(int i = 0; i < m; i++){
       cin >> E[i].x >> E[i].y >> E[i].w;
       E[i].x--, E[i].y--;
       E[i].id = i;
    }
    for(int i = 0; i < n; i++){
       make_set(i);
    }
    sort(E.begin(), E.end(), cmp);
    int cost = 0;
    for(auto e : E){
        if(find(e.x) != find(e.y)){
            tree[e.x].push_back({e.y, e.w});
            tree[e.y].push_back({e.x, e.w});
            unite(e.x, e.y);
            cost += e.w;
        }
    }
    dfs(0, 0, INT_MAX);
    while(q--){
        int r;
        cin >> r;
        r--;
        cout << ans[r] << endl;
    }

}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...