Submission #1268136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268136		29ChuManhTich	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	162 ms	32804 KiB

sightseeing

#include<bits/stdc++.h>
using namespace std;

#define NAME "FOX"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define ii pair<int, int>
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                                \
    cout.tie(NULL);
#define BIT(x, i) ((x >> i) & 1)
#define ALL(x) x.begin(), x.end()

const int maxn = 5e5 + 11;
const int LOGN = 20;
const int INF = 1e12 + 7;

int n, m, q;

struct Edge {
    int u, v, w;
    bool operator < (Edge &o) {
        return w > o.w;
    }
} edge[maxn];

struct DSU {
    int N, p[maxn], sz[maxn];
    void init(int n) {
        N = n;
        FOR(i, 1, N) p[i] = i, sz[i] = 1;
    }

    int find_set(int u) {
        return (u == p[u]) ? u : p[u] = find_set(p[u]);
    }

    bool united(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if(u == v) return false;

        if(sz[u] > sz[v]) swap(u, v);
        sz[u] += sz[v];
        p[v] = u;
        return true;
    }
};

vector<ii> adj[maxn];
int res[maxn];

void dfs(int u, int par, int qua) {
    for(ii p : adj[u]) {
        int v = p.fi, w = p.se;
        if (v == par) continue;
        int newqua = min(qua, w);
        res[v] = newqua;
        dfs(v, u, newqua);
    }
}


signed main() {
    fastIO;

    cin >> n >> m >> q;
    FOR(i, 1, m) {
        int u, v, w; cin >> u >> v >> w;
        edge[i] = {u, v, w};
    }

    DSU dsu; dsu.init(n + 5);
    sort(edge + 1, edge + m + 1);

    int cnt = 0;
    FOR(i, 1, m) {
        if(cnt >= n - 1) break;

        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if(dsu.united(u, v)) {
            cnt++;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }

    FOR(i, 1, n) res[i] = INF;

    dfs(1, 0, INF);

    FOR(i, 1, q) {
        int x; cin >> x;
        cout << res[x] << "\n";
    }

    return 0;
}

/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
3
4
*/

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