Submission #1288083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288083		hoangphuc210108	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1758 ms	205352 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define fi first
#define se second
const int MAX = 5e5 + 10;
typedef pair <int, int> ii;
typedef pair <int, ii> iii;

vector <iii> in;
vector <ii> g[MAX];

int par[MAX], sz[MAX], n, q, m;

int act(int v)
{
    if (par[v] == v) return v;

    par[v] = act(par[v]);
    return par[v];
}

bool innit(int x, int y)
{
    int a = act(x);
    int b = act(y);

    if(a == b ) return false;

    if(sz[a] < sz[b]) swap(a, b);

    par[b] = a;
    sz[a] += sz[b];
    return true;
}

bool ope(iii a, iii b)
{
return a.fi > b.fi;
}

int dist[MAX];

void dfs(int u, int par)
{
    for(auto x : g[u]){
        int v = x.fi;
        int w = x.se;
        if(v != par){
            dist[v] = min(dist[u], w);
            dfs(v, u);
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);

    cin >> n >> m >> q;

    for(int i = 1; i <= n; i++){
        par[i] = i;
        sz[i] = 1;
    }

    for(int i = 1; i <= m; i++){
        int x, y, val; cin >> x >> y >> val;

        in.push_back({val, {x, y}});
    }

    sort(in.begin(), in.end(), ope);

    for(int i = 0; i < m; i++){
        int u = in[i].se.fi;
        int v = in[i].se.se;
        int w = in[i].fi;

        if(innit(u, v)){
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }
    }
    dist[1] = 1e9;
    dfs(1, -1);

    while(q--){
        int x; cin >> x;
        cout << dist[x] << "\n";
    }
    return 0;

}

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