Submission #13022

#	Time	Username	Problem	Language	Result	Execution time	Memory
13022		gs14004	Sightseeing (NOI14_sightseeing)	C++98	25 / 25	2732 ms	93468 KiB

sightseeing

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> pi;

struct edge{int s,e,x;}a[5000005];
bool operator<(edge a, edge b){return a.x > b.x;}

struct disj{
    int pa[500005], r[500005];
    void init(int n){
        for(int i=0; i<=n; i++) pa[i] = i;
    }
    int find(int x){
        if(pa[x] == x) return x;
        return pa[x] = find(pa[x]);
    }
    bool uni(int p, int q){
        p = find(p);
        q = find(q);
        if(p == q) return 0;
        if(r[p] < r[q]) pa[q] = p;
        else pa[p] = q;
        if(r[p] == r[q]) r[p]++;
        return 1;
    }
}disj;

int n,m,qr;

vector<pi> graph[500005];
queue<int> q,pa,d;
int ret[500005];

int main(){
    scanf("%d %d %d",&n,&m,&qr);
    for (int i=0; i<m; i++) {
        scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
    }
    sort(a,a+m);
    disj.init(n);
    for (int i=0; i<m; i++) {
        if(disj.uni(a[i].s,a[i].e)){
            graph[a[i].s].push_back(pi(a[i].x,a[i].e));
            graph[a[i].e].push_back(pi(a[i].x,a[i].s));
        }
    }
    q.push(1);
    pa.push(0);
    d.push(1e9);
    while (!q.empty()) {
        int qf = q.front();
        int pf = pa.front();
        int df = d.front();
        q.pop();
        pa.pop();
        d.pop();
        ret[qf] = df;
        for (int i=0; i<graph[qf].size(); i++) {
            if(pf == graph[qf][i].second) continue;
            q.push(graph[qf][i].second);
            pa.push(qf);
            d.push(min(graph[qf][i].first,df));
        }
    }
    while (qr--) {
        int t;
        scanf("%d",&t);
        printf("%d\n",ret[t]);
    }
}

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