oj.uz

Submission #8131

# Submission time Handle Problem Language Result Execution time Memory
8131 2014-08-31T06:48:18 Z baneling100 Sightseeing (NOI14_sightseeing) C++
15 / 25
 3500 ms 165148 KB 
#include <stdio.h>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

pair <int,int> Road[10000001];
pair <int,int> Heap[5000001];
int V, E, Q, D[500001], Check[500001], Size, Next[10000001], Loc[500001], Start[500001];

void input(void) {

    int i, v1, v2, q;

    scanf("%d %d %d",&V,&E,&Q);
    for(i=1 ; i<=E ; i++) {
        scanf("%d %d %d",&v1,&v2,&q);
        if(!Start[v1])
            Start[v1]=2*i-1;
        Next[Loc[v1]]=2*i-1;
        Loc[v1]=2*i-1;
        Road[2*i-1]=make_pair(v2,q);
        if(!Start[v2])
            Start[v2]=2*i;
        Next[Loc[v2]]=2*i;
        Loc[v2]=2*i;
        Road[2*i]=make_pair(v1,q);
    }
}

void process(void) {

    int i, Now, Value;

    for(i=2 ; i<=V ; i++)
        D[i]=-1;
    D[1]=INF;
    Size=1;
    Heap[0]=make_pair(D[1],1);
    while(Size) {
        Now=Heap[0].second;
        pop_heap(Heap,Heap+Size);
        Size--;
        if(Check[Now])
            continue;
        Check[Now]=1;
        i=Start[Now];
        while(i) {
            Value=min(D[Now],Road[i].second);
            if(D[Road[i].first]<Value) {
                D[Road[i].first]=Value;
                Heap[Size++]=make_pair(Value,Road[i].first);
                push_heap(Heap,Heap+Size);
            }
            i=Next[i];
        }
    }
}

void output(void) {

    int i, X;

    for(i=1 ; i<=Q ; i++) {
        scanf("%d",&X);
        printf("%d\n",D[X]);
    }
}

int main(void) {

    input();
    process();
    output();

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 165148 KB Output is correct
2 Correct 16 ms 165148 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 165148 KB Output is correct
2 Correct 16 ms 165148 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 165148 KB Output is correct
2 Correct 28 ms 165148 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2932 ms 165148 KB Output is correct
2 Execution timed out 3500 ms 165148 KB Program timed out