Submission #676398

#TimeUsernameProblemLanguageResultExecution timeMemory
676398baneCrocodile's Underground City (IOI11_crocodile)C++14
0 / 100
1 ms212 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <unordered_set> #include <vector> #include <climits> #include <list> using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using llu = unsigned long long; using str = string; // yay python! // pairs using pii = pair<int,int>; using pll = pair<ll,ll>; using pdb = pair<db,db>; #define mp make_pair #define fr first #define sc second #define tcT template<class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pii>; using vpl = V<pll>; using vpd = V<pdb>; #define ms0(x) memset(x , 0, sizeof(x)) // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); } tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); } // loops #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) const int MOD = (int)1e9+7; // 998244353; const int MX = (int)2e5+5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4] = {0,1,0,-1}; const int dy[4] = {-1,0,1,0}; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ ll dp[N + 1]; ll dist[N + 1]; for (int i = 0; i<=N; i++){ dp[i]=1e18; dist[i] = 1e18; } priority_queue<pair<ll, int>>q; for (int i = 0; i < K; i++){ dp[P[i]] = 0; q.push(mp(0,P[i])); } vector<pair<int,int>>edges[N + 1]; for (int i = 0; i<M; i++){ edges[R[i][0]].pb(mp(R[i][1], L[i])); edges[R[i][1]].pb(mp(R[i][0], L[i])); } while(!q.empty()){ ll distt = -q.top().fr; int node = q.top().sc; q.pop(); if (dp[node] != distt)continue; //cout<<node<<" "<<distt<<endl; for (auto edge : edges[node]){ ll nx = dp[edge.fr]; if (nx > distt + edge.sc){ dp[edge.fr] = distt + edge.sc; q.push(mp( - (distt + edge.sc ), edge.fr)); } } } priority_queue<pair<ll,int>>traverse; traverse.push(mp(0,0)); ll ans = 1e9 + 1; dist[0]=0; int visited[N + 1]; memset(visited, 0, sizeof(visited)); while(!traverse.empty()){ ll distt = -traverse.top().fr; int node = traverse.top().sc; visited[node] = 1; traverse.pop(); //cout<<node<<" "<<distt<<endl; if (distt != dist[node])continue; ll smallest = 1e18; ll smallest_ind = -1; ll second_ind = -1; ll second = 1e18; for (int i = 0; i< (int) edges[node].size(); i++){ if (visited[edges[node][i].fr])continue; pair<int,ll>edge = edges[node][i]; if (dp[edge.fr] + edge.sc < smallest){ swap(second_ind, smallest_ind); swap(smallest, second); smallest = dp[edge.fr] + edge.sc; smallest_ind = i; }else if (dp[edge.fr] + edge.sc< second){ second = dp[edge.fr] + edge.sc; second_ind = i; } } if (second_ind == -1 || smallest_ind == -1){ //cout<<"no solution"; continue; } //cout<<edges[node][smallest_ind].fr<<" "<<edges[node][second_ind].fr<<endl; if (dist[edges[node][second_ind].fr] > distt + edges[node][second_ind].sc){ dist[edges[node][second_ind].fr] = distt + edges[node][second_ind].sc; traverse.push(mp(-dist[edges[node][second_ind].fr], edges[node][second_ind].fr)); } } for (int i = 0; i<K; i++){ ans = min(ans, dist[P[i]]); } return (int)ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...