Submission #1041708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041708		NeroZein	Board Game (JOI24_boardgame)	C++17	17 / 100	511 ms	1048576 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

using arr = array<long long, 3>;

const int N = 50004;
const long long INF = (int) 1e15;

char c[N]; 
vector<int> g[N];

vector<vector<long long>> dijkstra(int n, int src) {
  vector<vector<long long>> ret(3, vector<long long> (n + 1, INF)); 
  ret[0][src] = 0;
  priority_queue<arr, vector<arr>, greater<arr>> pq;
  pq.push({0, 0, src});
  while (!pq.empty()) {
    auto [cost, st, v] = pq.top();
    pq.pop();
    if (cost != ret[st][v]) {
      continue;
    }
    int nst = st + (c[v] == '1');
    for (int u : g[v]) {
      if (nst < 3 && cost + 1 < ret[nst][u]) {
        ret[nst][u] = cost + 1;
        pq.push({ret[nst][u], nst, u}); 
      }
    }
  }
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u); 
  }
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  vector<int> x(k);
  for (int i = 0; i < k; ++i) {
    cin >> x[i]; 
  }
  vector<vector<long long>> mn(2, vector<long long>(n + 1, INF)); 
  vector<vector<long long>> dist1 = dijkstra(n, x[0]);
  int cnt = count(c + 1, c + 1 + n, '1'); 
  vector<vector<vector<long long>>> dist(cnt);
  for (int i = 1, cur = 0; i <= n; ++i) {
    if (c[i] == '1') {
      dist[cur] = dijkstra(n, i);
      for (int j = 1; j <= n; ++j) {
        mn[0][j] = min(mn[0][j], dist[cur][1][j]);
        mn[1][j] = min(mn[1][j], dist[cur][2][j]); 
      }
      cur++; 
    }
  }
  vector<long long> s(2);
  for (int i = 1; i < k; ++i) {
    s[0] += mn[0][x[i]];
    s[1] += mn[1][x[i]];
  }
  for (int i = 1; i <= n; ++i) {
    long long ans = dist1[0][i];
    ans = min(ans, dist1[1][i] + s[0]);
    ans = min(ans, dist1[2][i] + s[1]); 
    cout << ans << '\n';
  }
  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9