Submission #345738

#	Time	Username	Problem	Language	Result	Execution time	Memory
345738		casperwang	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	703 ms	73056 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
 
const int MAXN = 100000;
const ll INF = 1e18;
vector <vector<pii>> path;
vector <pii> dis;
vector <bool> vis;
priority_queue <pii, vector<pii>, greater<pii>> nxt;
 
void init(int N) {
  path.clear();
  path.resize(N);
  dis.clear();
  dis.resize(N);
  vis.clear();
  vis.resize(N);
  for (int i = 0; i < N; i++)
    dis[i].ff = dis[i].ss = INF;
  while (nxt.size()) nxt.pop();
}
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  init(N);
  for (int i = 0; i < M; i++) {
    path[R[i][0]].pb(R[i][1], L[i]);
    path[R[i][1]].pb(R[i][0], L[i]);
  }
  for (int i = 0; i < K; i++) {
    dis[P[i]].ff = dis[P[i]].ss = 0;
    nxt.push(pii(0, P[i]));
  }
  while (nxt.size()) {
    ll now = nxt.top().ss, d = nxt.top().ff;
    nxt.pop();
    if (vis[now]) continue;
    vis[now] = 1;
    for (pii e : path[now]) {
      ll id = e.ff, c = e.ss;
      if (d + c <= dis[id].ff) {
        dis[id].ss = dis[id].ff;
        dis[id].ff = d + c;
        if (dis[id].ss < INF)
          nxt.push(pii(dis[id].ss, id));
      } else if (d + c < dis[id].ss) {
        dis[id].ss = d + c;
        nxt.push(pii(dis[id].ss, id));
      }
    }
  }
  return (int)dis[0].ss;
}

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