Submission #910388

#TimeUsernameProblemLanguageResultExecution timeMemory
910388oblantisCrocodile's Underground City (IOI11_crocodile)C++17
89 / 100
405 ms75436 KiB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const ll inf = 1e15; const int mod = 1e9+7; const int maxn = 2e5 + 1; #include "crocodile.h" ll dst[maxn][2]; vt<pii> g[maxn]; int travel_plan(int n, int m, int adj[][2], int l[], int k, int p[]){ for(int i = 0; i < m; i++){ g[adj[i][0]].pb({adj[i][1], l[i]}); g[adj[i][1]].pb({adj[i][0], l[i]}); } for(int i = 0; i < n; i++){ dst[i][0] = dst[i][1] = inf; } priority_queue<pll, vt<pll>, greater<pll>> pq; for(int i = 0; i < k; i++){ dst[p[i]][0] = dst[p[i]][1] = 0; pq.push({0, p[i]}); } while(!pq.empty()){ pll nw = pq.top(); pq.pop(); if(dst[nw.ss][1] != nw.ff)continue; for(auto i : g[nw.ss]){ if(nw.ff + i.ss >= dst[i.ff][1])continue; if(nw.ff + i.ss < dst[i.ff][0]){ dst[i.ff][1] = dst[i.ff][0]; dst[i.ff][0] = nw.ff + i.ss; } else dst[i.ff][1] = nw.ff + i.ss; pq.push({dst[i.ff][1], i.ff}); } } return dst[0][1]; } //void solve() { //int n, m, k; //cin >> n >> m >> k; //int r[m][2], l[m], p[k]; //for(int i = 0; i < m; i++){ //cin >> r[i][0] >> r[i][1] >> l[i]; //} //for(int i = 0; i < k; i++)cin >> p[i]; //cout << travel_plan(n, m, r, l, k, p); //} //int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //int times = 1; ////cin >> times; //for(int i = 1; i <= times; i++) { //solve(); //} //return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...