Submission #14659

#	Time	Username	Problem	Language	Result	Execution time	Memory
14659		club4208	Sightseeing (NOI14_sightseeing)	C++98	0 / 25	2657 ms	203616 KiB

sightseeing

#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 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 10