Submission #37872

#	Time	Username	Problem	Language	Result	Execution time	Memory
37872		14kg	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	973 ms	152320 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11