Submission #258172

#TimeUsernameProblemLanguageResultExecution timeMemory
258172monus1042Crocodile's Underground City (IOI11_crocodile)C++17
0 / 100
2 ms2688 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef long long ll; typedef pair<int,int> ii; typedef vector<ii> vii; #define pb push_back #define mkp make_pair #define all(X) X.begin(), X.end() const int MAXS = 100002; vector< pair<int, ll> > g[MAXS]; priority_queue < pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll,int> > > pq; ll d[MAXS]; int state[MAXS]; // 0 unvisited, 1 has first val, 2 totally updated void dj(){ while(!pq.empty()){ int auxu = pq.top().second; ll w = pq.top().first; pq.pop(); for (int i=0; i<g[auxu].size(); i++){ int v = g[auxu][i].first; ll wuv = g[auxu][i].second + w; if (state[v] == 2) continue; if (state[v] == 0){ state[v]=1; d[v] = wuv; if (v != 0) pq.push(mkp(wuv, v)); } if (state[v] == 1){ state[v] = 2; d[v] = wuv; if (v != 0) pq.push(mkp(wuv, v)); } } } } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ for (int i=0; i<M; i++){ g[ R[i][0] ].pb(ii( R[i][1] , L[i])); g[ R[i][1] ].pb(ii( R[i][0] , L[i])); } for (int i=0; i<K; i++){ pq.push(mkp(0, P[i])); d[P[i]]=0; state[P[i]]=2; } dj(); return (int)d[0]; }

Compilation message (stderr)

crocodile.cpp: In function 'void dj()':
crocodile.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<g[auxu].size(); i++){
                   ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...