oj.uz

Submission #14659

# Submission time Handle Problem Language Result Execution time Memory
14659 2015-05-25T07:17:29 Z club4208 Sightseeing (NOI14_sightseeing) C++
0 / 25
 2657 ms 203616 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define MV 500001
using namespace std;
struct es{
    int from, to, cost;
}edge[5000001];
int V, E, Q;
int QL[500001];
int par[500001], rank[500001];
vector<es> G[MV];
void add_edge(es e){
    G[e.from].push_back((es){e.from,e.to,e.cost});
    G[e.to].push_back((es){e.to,e.from,e.cost});
}
void init(){
    for(int i=0;i<=V;i++){
        par[i]=i;
        rank[i]=0;
    }
}
int find(int x){
    if(x==par[x]) return x;
    return par[x]=find(par[x]);
}
bool same(int x,int y){
    return find(x)==find(y);
}
void unite(int x,int y){
    if(same(x,y)) return;
    if(rank[x]>rank[y]){
        par[y]=x;
    }
    else{
        par[x]=y;
        if(rank[x]==rank[y]) rank[y]++;
    }
}
bool cmp(const es &e1, const es &e2){
    return e1.cost>e2.cost;
}
bool visited[500001];
int dist[500001];
void dfs(int x, int m){
    visited[x]=true; dist[x]=m;
    for(int i=0;i<G[x].size();i++){
        if(!visited[G[x][i].to]){
            dfs(G[x][i].to, m);
        }
    }
}
int main(){
    scanf("%d %d %d", &V, &E, &Q);
    for(int i=0;i<E;i++){
        scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].cost);
        //add_edge(edge[i]);
    }
    init();
    sort(edge, edge+E, cmp);
    for(int i=0;i<E;i++){
        int tmp1, tmp2, tmp3;
        tmp1=find(1);
        tmp2=find(edge[i].from);
        tmp3=find(edge[i].to);
        if(tmp1==tmp2 && tmp1!=tmp3 && !visited[edge[i].to]) dfs(edge[i].to, edge[i].cost);
        if(tmp1==tmp3 && tmp2!=tmp3 && !visited[edge[i].from]) dfs(edge[i].from, edge[i].cost);
        unite(edge[i].from, edge[i].to);
        add_edge(edge[i]);
    }
    for(int i=0;i<Q;i++){
        int tmp;
        scanf("%d", &tmp);
        printf("%d\n", dist[tmp]);
    }
    return 0;
}

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 79828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 79960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 81808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2657 ms 203616 KB Output isn't correct
2 Halted 0 ms 0 KB -