oj.uz

답안 #13022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13022 2015-01-26T03:51:44 Z gs14004 관광 (NOI14_sightseeing) C++
25 / 25
 2732 ms 93468 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 77760 KB Output is correct
2 Correct 0 ms 77760 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 77760 KB Output is correct
2 Correct 2 ms 77760 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 78948 KB Output is correct
2 Correct 28 ms 78948 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1721 ms 90960 KB Output is correct
2 Correct 2732 ms 93468 KB Output is correct