Submission #1362143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362143		hieuminh	Crocodile's Underground City (IOI11_crocodile)	C++20	89 / 100	212 ms	46872 KiB

crocodile

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define forr(i, a, b) for (int i = a; i <= b; i++)
#define rfor(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 1e5 + 5;

int d1[maxn], d2[maxn];
struct s {
  int id;
  int dist;
  bool operator<(const s &o) const {
    return dist > o.dist;
  }
};
vector<s> adj[maxn];
priority_queue<s> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  cin.tie(0)->sync_with_stdio(0);
  forr(i, 0, N - 1) {
    d1[i] = d2[i] = 1e18;
    adj[i].clear();
  }
  forr(i, 0, K - 1) {
    pq.push({P[i], 0});
    d1[P[i]] = d2[P[i]] = 0;
  }
  forr(i, 0, M - 1) {
    int u = R[i][0], v = R[i][1], w = L[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  while (!pq.empty()) {
    int u = pq.top().id, dist = pq.top().dist;
    pq.pop();
    if (dist > d2[u])
      continue;
    for (auto &[v, w] : adj[u]) {
      if (d2[u] + w < d1[v]) {
        d2[v] = d1[v];
        d1[v] = d2[u] + w;
        if (d2[v] < 1e18)
          pq.push({v, d2[v]});
      } else if (d2[u] + w < d2[v]) {
        d2[v] = d2[u] + w;
        pq.push({v, d2[v]});
      }
    }
  }
  return d2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:21:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 |     d1[i] = d2[i] = 1e18;
      |                     ^~~~

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