제출 #1355371

#제출 시각아이디문제언어결과실행 시간메모리
1355371michael12관광 (NOI14_sightseeing)C++20
15 / 25
1262 ms327680 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 int long long
#define ss second
const int inf = 1e18;
#define endl '\n'
const int maxn = 500005;
const int LG = 20;
int up[maxn][LG];
int mx[maxn][LG];
int depth[maxn];
int n, m;
vector<pair<int, int>> tree[maxn];
void dfs(int u, int p, int w){
    up[u][0] = p;
    mx[u][0] = w;
    for(int i = 1; i < LG; i++){
        up[u][i] = up[up[u][i - 1]][i - 1];
        mx[u][i] = min(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
    }
    for(auto t : tree[u]){
        if(t.ff == p) continue;
        depth[t.ff] = depth[u] + 1;
        dfs(t.ff, u, t.ss);
    }
}
int get(int u, int v){
    int ans = inf;
    if(depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for(int i = 0; i < LG; i++){
        if(diff & (1 << i)){
            ans = min(ans, mx[u][i]);
            u = up[u][i];
        }
    }
    for(int i = LG - 1; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            ans = min(ans, mx[u][i]);
            ans = min(ans, mx[v][i]);
            u = up[u][i];
            v = up[v][i];
        }
    }
    return min({ans, mx[u][0], mx[v][0]});
}
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, inf);
    while(q--){
        int r;
        cin >> r;
        r--;
        cout << get(0, r) << endl;
    }




    


}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…