Submission #36351

#	Time	Username	Problem	Language	Result	Execution time	Memory
36351		funcsr	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1529 ms	174380 KiB

crocodile

#include <iostream>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define _1 first
#define _2 second
typedef pair<int, int> P;

int N, M;
vector<P> G[100000];
priority_queue<P, vector<P>, greater<P> > Q;
int dp[100000];
bool flag[100000], used[100000];
void set(int x, int val) {
  used[x] = true;
  dp[x] = val;
  for (P p : G[x]) {
    int t = p._1, l = p._2;
    Q.push(P(val+l, t));
  }
}

int travel_plan(int n, int m, int R[][2], int L[], int K, int p[]) {
  N = n, M = m;
  rep(i, M) {
    G[R[i][0]].pb(P(R[i][1], L[i]));
    G[R[i][1]].pb(P(R[i][0], L[i]));
  }
  rep(i, N) dp[i] = INF, flag[i] = used[i] = false;
  rep(i, K) {
    int x = p[i];
    set(x, 0);
  }
  while (!Q.empty()) {
    int val = Q.top()._1, x = Q.top()._2;
    Q.pop();
    if (used[x]) continue;
    if (flag[x]) set(x, val);
    else flag[x] = true;
  }
  return dp[0];
}

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