| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 910392 | 2024-01-18T04:44:34 Z | oblantis | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#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 = 1e5 + 1;
#include "crocodile.h"
ll dst[maxn][2];
vt<pii> g[maxn];
ll 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;
//}