Submission #1268135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268135		29ChuManhTich	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	150 ms	22000 KiB

sightseeing

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

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ii pair<int,int>
#define fi first
#define se second

const int maxn = 5e5 + 11;
int n, m, q;

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

struct DSU {
    int p[maxn], sz[maxn];
    void init(int 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 bfs(int start) {
    queue<int> q;
    res[start] = INT_MAX;
    q.push(start);
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(auto [v,w] : adj[u]) {
            if(res[v]==-1) { // chưa thăm
                res[v] = min(res[u], w);
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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);
    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] = -1;
    bfs(1);

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

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