oj.uz

Submission #18381

# Submission time Handle Problem Language Result Execution time Memory
18381 2016-01-30T07:34:51 Z atomzeno Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 678 ms 176428 KB 
#include "crocodile.h"
#include<vector>
#include<algorithm>
#include<queue>
#define NN 100001
#define MM 1000001
using namespace std;
int n,m,k,num[NN];
long long val[NN][2];
bool check[NN];
struct ST{int s,e,val;}A[MM];
struct SST{int s,val;}B[MM],o;
vector<SST> ND[NN];
priority_queue<pair<int,int> > bfs;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    int i;
    int loc2,val2,loc,len;
    n=N,m=M,k=K;
    for(i=0;i<n;i++){
        val[i][0]=val[i][1]=1000000001;
        check[i]=0;
    }
    for(i=0;i<m;i++){A[i].s=R[i][0],A[i].e=R[i][1],A[i].val=L[i];}
    for(i=0;i<m;i++){
        o.s=A[i].s,o.val=A[i].val;
        ND[A[i].e].push_back(o);
        o.s=A[i].e,o.val=A[i].val;
        ND[A[i].s].push_back(o);
        num[A[i].e]++,num[A[i].s]++;
    }
    for(i=0;i<k;i++){
        val[P[i]][0]=0,val[P[i]][1]=0;
        bfs.push(make_pair(0,P[i]));
    }
    for(;!bfs.empty();){
        loc=(bfs.top()).second;
        if(check[loc]==0){
            len=num[loc];
            for(i=0;i<len;i++){
                if(val[ND[loc][i].s][0]>(val[loc][1]+ND[loc][i].val)){
                    val[ND[loc][i].s][1]=val[ND[loc][i].s][0];
                    val[ND[loc][i].s][0]=(val[loc][1]+ND[loc][i].val);
                    bfs.push(make_pair(val[ND[loc][i].s][1]*(-1),ND[loc][i].s));
                }
                else if(val[ND[loc][i].s][1]>(val[loc][1]+ND[loc][i].val)){
                    val[ND[loc][i].s][1]=(val[loc][1]+ND[loc][i].val);
                    bfs.push(make_pair(val[ND[loc][i].s][1]*(-1),ND[loc][i].s));
                }
            }
            check[loc]=1;
        }
        bfs.pop();
    }
    return val[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 170964 KB Output is correct
2 Correct 134 ms 149116 KB Output is correct
3 Correct 116 ms 150336 KB Output is correct
4 Correct 678 ms 176428 KB Output is correct
5 Correct 297 ms 165636 KB Output is correct
6 Correct 55 ms 145576 KB Output is correct
7 Correct 386 ms 161560 KB Output is correct