Submission #1003474

#TimeUsernameProblemLanguageResultExecution timeMemory
1003474HasanV11010238Crocodile's Underground City (IOI11_crocodile)C++17
46 / 100
2 ms1116 KiB
#include "crocodile.h" #include <bits/stdc++.h> #define ll long long #define INF 1000000000 using namespace std; vector<vector<vector<ll>>> v; vector<ll> vis, dp, isw, dpmi, lawi, di; void dfs(int x, ll co, ll last){ vis[x] = 1; vector<ll> pus = {INF}; if (isw[x] == 1){ dp[x] = co; last = co; } di[x] = co; lawi[x] = last; for (auto el : v[x]){ if (vis[el[1]] == 2){ ll difr = di[el[1]] - (di[x] + el[0]); ll va = dpmi[el[1]] - difr; ll va2 = el[0] + di[el[1]] - lawi[el[1]]; if (lawi[el[1]] >= INF && dpmi[el[1]] >= INF){ pus.push_back(INF); } else{ pus.push_back(max(va, va2)); } } if (vis[el[1]] == 0){ dfs(el[1], co + el[0], last); pus.push_back(dp[el[1]]); } } ll mi = INF, smi = INF; for (int i = 0; i < pus.size(); i++){ if (pus[i] <= mi){ smi = mi; mi = pus[i]; } else if (pus[i] <= smi){ smi = pus[i]; } } if (isw[x] == 1){ dp[x] = co; dpmi[x] = co; vis[x] = 2; return; } dp[x] = smi; dpmi[x] = mi; vis[x] = 2; } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { v.resize(N), vis.assign(N, 0), dp.assign(N, 0), isw.assign(N, 0), dpmi.assign(N, 0), lawi.assign(N, 0), di.assign(N, 0); for (int i = 0; i < M; i++){ v[R[i][0]].push_back({L[i], R[i][1]}); v[R[i][1]].push_back({L[i], R[i][0]}); } for (int i = 0; i < N; i++){ dp[i] = 0; sort(v[i].begin(), v[i].end()); } for (int i = 0; i < K; i++){ isw[P[i]] = 1; } dfs(0, 0, INF); return dp[0]; }

Compilation message (stderr)

crocodile.cpp: In function 'void dfs(int, long long int, long long int)':
crocodile.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 0; i < pus.size(); i++){
      |                   ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...