Submission #207380

#TimeUsernameProblemLanguageResultExecution timeMemory
207380robsCrocodile's Underground City (IOI11_crocodile)C++17
100 / 100
1432 ms58832 KiB
#include "crocodile.h" #include <bits/stdc++.h> #define debug(args...) //fprintf(stderr, args) #define mk make_pair using namespace std; const int maxn = 2e5, INF = 1e9; int dist[maxn],distMin[maxn],marcExit[maxn],contExit[maxn],resp,n; vector<int> grafo[maxn]; vector<int> peso[maxn]; vector<int> casos[maxn]; set<pair<int, int> > fora; void dijkstra() { debug("dijkstra\n"); debug("set foi!!\n"); debug("criei os set ai\n"); for(int x = 0; x < n; x++) fora.insert( mk(dist[x], x)); debug("inicializei dnv\n"); while(!fora.empty()) { int cur = fora.begin()->second; debug(" %d:\n",cur); fora.erase(fora.begin()); for(int x = 0; x < grafo[cur].size(); x++) { int viz = grafo[cur][x]; debug(" %d\n",viz); int p = peso[cur][x]; if(dist[cur] + p < distMin[viz]) { fora.erase( mk(dist[viz], viz)); dist[viz] = distMin[viz]; distMin[viz] = dist[cur] + p; fora.insert( mk(dist[viz], viz)); continue; } if(dist[cur] + p < dist[viz]) { fora.erase( mk(dist[viz], viz)); dist[viz] = dist[cur] + p; fora.insert( mk(dist[viz], viz)); } } } } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { debug("comeco\n"); n = N; for(int x = 0; x < K; x++) marcExit[P[x]] = 1; for(int x = 0; x < M; x++) { int i = R[x][0]; int j = R[x][1]; int p = L[x]; grafo[i].push_back(j); grafo[j].push_back(i); peso[i].push_back(p); peso[j].push_back(p); if(marcExit[i] && marcExit[j]) continue; if(marcExit[i]) contExit[j]++; if(marcExit[j]) contExit[i]++; } debug("criou o grafo\n"); for(int x = 0; x < N; x++) { if(marcExit[x]) { distMin[x] = 0; dist[x] = 0; } else { distMin[x] = INF; dist[x] = INF; } if(contExit[x] >= 2) { int Min = INF; int Max = INF; for(int y = 0; y < grafo[x].size(); y++) { int viz = grafo[x][y]; int p = peso[x][y]; if(dist[viz] + p < Min) { Max = Min; Min = dist[viz] + p; continue; } if(dist[viz] + p < Max) Max = dist[viz] + p; } dist[x] = Max; } } debug("terminei a entrada\n"); dijkstra(); debug("foi o dijkstra\n"); int resp = dist[0]; debug("resp = %d\n",resp); return resp; }

Compilation message (stderr)

crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int x = 0; x < grafo[cur].size(); x++)
                  ~~^~~~~~~~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int y = 0; y < grafo[x].size(); y++)
                   ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...