Submission #410341

#TimeUsernameProblemLanguageResultExecution timeMemory
410341600MihneaCrocodile's Underground City (IOI11_crocodile)C++17
100 / 100
1938 ms74060 KiB
#include <bits/stdc++.h> #include "crocodile.h" using namespace std; const int N = 100000 + 7; const int INF = (int) 1e9 + 7; int n, m, k, best[N]; vector<pair<int, int>> lol[N]; vector<pair<int, int>> g[N]; priority_queue<pair<int, int>> q; int lt[N], step; void push(int i, int value) { for (auto &it : g[i]) { lol[it.first].push_back({min(INF, value + it.second), i}); sort(lol[it.first].begin(), lol[it.first].end()); step++; vector<pair<int, int>> lol2; for (auto &k : lol[it.first]) { if (lt[k.second] != step) { lol2.push_back(k); lt[k.second] = step; if ((int) lol2.size() == 2) { break; } } } lol[it.first] = lol2; } best[i] = value; q.push({-best[i], i}); } int get_second(int a) { if ((int) lol[a].size() < 2) { return INF; } return lol[a][1].first; } int travel_plan(int nn, int mm, int r[][2], int len[], int kk, int ch[]) { n = nn; m = mm; k = kk; for (int i = 0; i < n; i++) { g[i].clear(); lol[i].clear(); best[i] = INF; } for (int i = 0; i < m; i++) { g[r[i][0]].push_back({r[i][1], len[i]}); g[r[i][1]].push_back({r[i][0], len[i]}); lol[r[i][0]].push_back({INF, r[i][1]}); lol[r[i][1]].push_back({INF, r[i][0]}); } for (int i = 0; i < k; i++) { push(ch[i], 0); } while (!q.empty()) { int a = q.top().second, o = -q.top().first; q.pop(); if (best[a] != o) { continue; } for (auto &it : g[a]) { int node = it.first, relax = get_second(node); if (relax < best[node]) { push(node, relax); } } } if (best[0] == INF) { best[0] = -1; } return best[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...