oj.uz

Submission #7699

# Submission time Handle Problem Language Result Execution time Memory
7699 2014-08-14T14:36:39 Z baneling100 Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 640 ms 152568 KB 
#include "crocodile.h"
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
static priority_queue <ppair,vector<ppair>,greater<ppair> > Q;
static vector <ppair> A[100000];
static int D[100000][2], Check[100000];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {

    int i, j, Now;

    for(i=0 ; i<M ; i++) {
        A[R[i][0]].push_back(make_pair(R[i][1],L[i]));
        A[R[i][1]].push_back(make_pair(R[i][0],L[i]));
    }
    for(i=0 ; i<N ; i++)
        D[i][0]=D[i][1]=INF;
    for(i=0 ; i<K ; i++) {
        D[P[i]][0]=D[P[i]][1]=0;
        Q.push(make_pair(0,P[i]));
    }
    while(!Q.empty()) {
        Now=Q.top().second;
        Q.pop();
        if(Check[Now])
            continue;
        Check[Now]=1;
        j=A[Now].size();
        for(i=0 ; i<j ; i++)
            if(!Check[A[Now][i].first]) {
                if(D[A[Now][i].first][0]>D[Now][1]+A[Now][i].second) {
                    D[A[Now][i].first][1]=D[A[Now][i].first][0];
                    D[A[Now][i].first][0]=D[Now][1]+A[Now][i].second;
                    if(D[A[Now][i].first][1]!=INF)
                        Q.push(make_pair(D[A[Now][i].first][1],A[Now][i].first));
                }
                else if(D[A[Now][i].first][1]>D[Now][1]+A[Now][i].second) {
                    D[A[Now][i].first][1]=D[Now][1]+A[Now][i].second;
                    Q.push(make_pair(D[A[Now][i].first][1],A[Now][i].first));
                }
            }
    }
    return D[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122108 KB Output is correct
2 Correct 0 ms 122108 KB Output is correct
3 Correct 0 ms 122108 KB Output is correct
4 Correct 0 ms 122108 KB Output is correct
5 Correct 0 ms 122108 KB Output is correct
6 Correct 0 ms 122108 KB Output is correct
7 Correct 0 ms 122108 KB Output is correct
8 Correct 0 ms 122108 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 122240 KB Output is correct
2 Correct 0 ms 122108 KB Output is correct
3 Correct 0 ms 122108 KB Output is correct
4 Correct 4 ms 122240 KB Output is correct
5 Correct 4 ms 122372 KB Output is correct
6 Correct 0 ms 122108 KB Output is correct
7 Correct 0 ms 122108 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 148648 KB Output is correct
2 Correct 80 ms 126728 KB Output is correct
3 Correct 88 ms 127916 KB Output is correct
4 Correct 640 ms 152568 KB Output is correct
5 Correct 348 ms 144840 KB Output is correct
6 Correct 48 ms 124352 KB Output is correct
7 Correct 352 ms 140456 KB Output is correct