Submission #1266412

#TimeUsernameProblemLanguageResultExecution timeMemory
1266412BlockOGCrocodile's Underground City (IOI11_crocodile)C++20
0 / 100
3 ms4928 KiB
#include "crocodile.h" #include <bits/stdc++.h> // mrrrow meeow :3 // go play vivid/stasis now! it's free on steam #define fo(i, a, b) for (auto i = (a); i < (b); i++) #define of(i, a, b) for (auto i = (b); i-- > (a);) #define f first #define s second #define pb push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define be(a) a.begin(), a.end() using namespace std; int ____init = [] { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); return 0; }(); map<int, int> adj[100000]; set<int> exits; int dist[100000]; int par[100000]; int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) { fo(i, 0, m) { adj[r[i][0]][r[i][1]] = l[i]; adj[r[i][1]][r[i][0]] = l[i]; } { fo(i, 0, n) dist[i] = 1000000001; priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q; fo(i, 0, k) { q.push({0, {p[i], -1}}); exits.insert(p[i]); } while (q.size()) { auto [d, e] = q.top(); auto [i, p] = e; q.pop(); if (d >= dist[i]) continue; dist[i] = d; par[i] = p; for (auto [j, l] : adj[i]) { if (dist[j] != 1000000001) continue; q.push({d + l, {j, i}}); } } fo(i, 0, n) if (par[i] != -1) adj[i].erase(par[i]), adj[par[i]].erase(i); } { fo(i, 0, n) dist[i] = 1000000001; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push({0, 0}); while (q.size()) { auto [d, i] = q.top(); q.pop(); if (d >= dist[i]) continue; dist[i] = d; if (exits.count(i)) return d; for (auto [j, l] : adj[i]) { if (dist[j] != 1000000001) continue; q.push({d + l, j}); } } } }

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...