oj.uz

Submission #37872

# Submission time Handle Problem Language Result Execution time Memory
37872 2017-12-28T11:44:18 Z 14kg Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 973 ms 152320 KB 
#include "crocodile.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#define N 100001
#define INF 2000000000

using namespace std;
int n;
bool check[N];
pair<int,int> d[N];
vector<pair<int,int> > r[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;

int travel_plan(int _n, int _m, int in1[][2], int in2[], int _k, int _p[]) {
    int x, y, z, t, temp;
    bool Q_check;

    n=_n;
    for(int i=0; i<_m; i++){
        x=in1[i][0]+1, y=in1[i][1]+1, z=in2[i];
        r[x].push_back({y,z}), r[y].push_back({x,z});
    }
    for(int i=1; i<=n; i++) d[i]={INF,INF};
    for(int i=0; i<_k; i++){
        x=_p[i]+1, d[x]={0,0};
        Q.push({0,x});
    }

    while(!Q.empty()){
        t=Q.top().first, x=Q.top().second, Q.pop();
        if(check[x]) continue;

        check[x]=true;
        for(vector<pair<int,int> >::iterator it=r[x].begin(); it!=r[x].end(); it++){
            temp=d[x].second+it->second, y=it->first;

            Q_check=false;
            if(d[y].first>temp){
                d[y].second=d[y].first, d[y].first=temp;
                Q_check=true;
            }
            else if(d[y].second>temp){
                d[y].second=temp;
                Q_check=true;
            }

            if(Q_check && d[y].second!=INF) Q.push({d[y].second,y});
        }
    } return d[1].second;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:17:18: warning: variable 't' set but not used [-Wunused-but-set-variable]
     int x, y, z, t, temp;
                  ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 148460 KB Output is correct
2 Correct 116 ms 126528 KB Output is correct
3 Correct 113 ms 127716 KB Output is correct
4 Correct 973 ms 152320 KB Output is correct
5 Correct 416 ms 144700 KB Output is correct
6 Correct 53 ms 124152 KB Output is correct
7 Correct 399 ms 140124 KB Output is correct