Submission #1025928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025928		NguyenPhucThang	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	351 ms	92608 KiB

crocodile

#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
#define oo 1e18
using namespace std;


ll travel_plan(int n, int m, int R[][2], int L[], int k, int p[]){
   vector<vector<pll>> g(n + 1);
   vector<bool> checked(n + 1);
   vector<vector<ll>> d(n + 1, vector<ll>(2));

   priority_queue<pll, vector<pll>, greater<pll>> pq;

   forf(i, 0, n) d[i][0] = d[i][1] = oo;

   forf(i, 0, m){
      ll x = R[i][0], y = R[i][1], w = L[i];
      g[x].pb({y, w});
      g[y].pb({x, w});
   }

   forf(i, 0, n) d[i][0] = d[i][1] = oo;

   forf(i, 0, k){
      d[p[i]][0] = d[p[i]][1] = 0;
      pq.push({d[p[i]][1], p[i]});
   }

   while (!pq.empty()){
      pll x = pq.top();
      pq.pop();
      int u = x.se;
      
      if (checked[u]) continue;
      checked[u] = true;

      for(pll e : g[u]){
         ll v = e.fi, w = e.se;
         if (d[v][0] > d[u][1] + w){
            if (d[v][0] != d[v][1] && d[v][0] < oo){
               d[v][1] = d[v][0];
               pq.push({d[v][1], v});
            }
            d[v][0] = d[u][1] + w;
         }
         else if (d[v][1] > d[u][1] + w){
            d[v][1] = d[u][1] + w;
            pq.push({d[v][1], v});
         }
      }
   }

   return d[0][1];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11