Submission #1290080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290080		G_thang_dizz_lenhi	Sightseeing (NOI14_sightseeing)	C++20	In queue	0 ms	0 KiB

sightseeing

#include<bits/stdc++.h>
typedef int ii;
typedef long long ll;

using namespace std;

const string name = "TINHCLDD";
const ii MOD = 1e9 + 7;
const ii N = 5e5 + 10;
const ii INF = 1e9 + 237;

ii n, m, q;
vector<pair<ii, ii>> edge[N];
vector<pair<ii, ii>> e[N];
ii dp[N];

void INP(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen((name + ".inp").c_str(),"r")){
        freopen((name + ".inp").c_str(),"r",stdin);
        freopen((name + ".out").c_str(),"w",stdout);
    }
    cin >> n >> m >> q;
    ii u, v, len;
    while(m--){
        cin >> u >> v >> len;
        edge[len].push_back({u, v});
    }
}

struct DSU{
    ii sz;vector<ii> par;

    void init(ii _sz){
        sz = _sz;
        par.resize(sz + 1);
        for (ii i = 1;i <= sz;i++) par[i] = i;
    }

    ii find_par(ii u){
        return (u == par[u] ? u : par[u] = find_par(par[u]));
    }

    bool connect(ii a,ii b){
        a = find_par(a);
        b = find_par(b);
        if (a == b) return false;
        par[a] = b;
        return true;
    }

} DSU;

void dfs(ii u, ii p){
    ii v, len;
    for(auto d : e[u]){
        tie(v, len) = d;
        if (v != p){
            dp[v] = min(dp[u], len);
            dfs(v, u);
        }
    }
}

int main(){
    INP();
    DSU.init(n);
    ii u, v, len;
    for (ii len = N - 1;len >= 0;len--)
    for (auto dir : edge[len]){
        tie(u, v) = dir;
        if (DSU.connect(u, v)){
            e[u].push_back({v, len});
            e[v].push_back({u, len});
//            cerr << u << " " << v << "\n";
        }
    }

    dp[1] = INF;
    dfs(1, 0);
    while(q--){
        cin >> u;
        cout << dp[u] << "\n";
    }
    cerr << 1000* clock() / CLOCKS_PER_SEC;
    return 0;
}

//NGT 1600-2000 cf
//1/200 hard quests