Submission #757773

#	Time	Username	Problem	Language	Result	Execution time	Memory
757773		taher	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	539 ms	89684 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

const long long inf = 200000000000000;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  int n = N;
  int m = M;
  int k = K;

  vector<vector<array<long long, 2>>> adj(n);
  for (int i = 0; i < m; i++) {
    int u = R[i][0];
    int v = R[i][1];
    int t = L[i];
    adj[u].push_back({v, t});
    adj[v].push_back({u, t});
  }
  vector<int> leaves(k);
  for (int i = 0; i < k; i++) {
    leaves[i] = P[i];
  }
  priority_queue<array<long long, 2>, vector<array<long long, 2>>, greater<array<long long, 2>>> pQue;
  
  vector<long long> d(n, inf);  // good
  vector<long long> p(n, inf);  // min
  vector<bool> done(n);
  vector<int> cnt(n);
  vector<bool> mark(n);
  for (auto x : leaves) {
    mark[x] = true;
    d[x] = 0;
    p[x] = 0;
    pQue.push({d[x], x});
  }
  while (!pQue.empty()) {
    auto t = pQue.top();
    pQue.pop();
    if (done[t[1]]) {
      continue;
    }
    done[t[1]] = true;
    for (auto x : adj[t[1]]) {
      cnt[x[0]]++;
      if (cnt[x[0]] == 1) {
        d[x[0]] = x[1] + t[0];
        p[x[0]] = x[1] + t[0];
      } else if (cnt[x[0]] == 2) {
        d[x[0]] = max(d[x[0]], x[1] + t[0]);
        p[x[0]] = min(p[x[0]], x[1] + t[0]);
        pQue.push({d[x[0]], x[0]});
      } else {
        if (x[1] + t[0] <= p[x[0]]) {
          d[x[0]] = p[x[0]];
          pQue.push({d[x[0]], x[0]});
          p[x[0]] = x[1] + t[0];
        } else if (x[1] + t[0] < d[x[0]]) {
          d[x[0]] = x[1] + t[0];
          pQue.push({d[x[0]], x[0]});
        }
      }
    }
  }
  return d[0];
}

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