Submission #446229

#	Time	Username	Problem	Language	Result	Execution time	Memory
446229		stat0r1c	Crocodile's Underground City (IOI11_crocodile)	C++11	89 / 100	568 ms	47628 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned ll;
template<typename T> using vt = vector<T>;
using vi = vt<int>;
using vvi = vt<vi>;
using ii = pair<int, int>;
using vii = vt<ii>;
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define debug(x) cerr << #x << " -> " << x << '\n'
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int inf = 1e9 + 7;
const ll infll = 1e18 + 10;
using pll = pair<ll, ll>;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  vt<vii> a(n);
  for(int i = 0; i < m; i++) {
    a[r[i][0]].eb(l[i],r[i][1]);
    a[r[i][1]].eb(l[i],r[i][0]);
  }
  vt<pll> d(n, {infll, infll});
  priority_queue<pll, vt<pll>, greater<pll>> pq;
  for(int i = 0; i < k; i++) {
    d[p[i]] = {0,0};
    pq.push({0, p[i]});  
  }
  while(!pq.empty()) {
    ll du = pq.top().F, u = pq.top().S;
    pq.pop();
    if(du != d[u].S || u == 0) continue;
    for(ii v : a[u]) {
      if(d[v.S].F > du + v.F) {
        d[v.S] = mp(du + v.F, d[v.S].F);
        if(d[v.S].S != infll) pq.push({d[v.S].S, v.S});
      }
      else if(d[v.S].S > du + v.F) pq.push({d[v.S].S = du + v.F, v.S});
    }
  }
  return d[0].S;
}

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