Submission #1316874

#TimeUsernameProblemLanguageResultExecution timeMemory
1316874LIABoard Game (JOI24_boardgame)C++17
3 / 100
4094 ms6404 KiB
//
// Created by liasa on 29/01/2026.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
#define pll pair<ll, ll>
ll n, m, k;
v<v<ll>> g;
v<ll> loc;
v<ll> s;
ll stop_cnt = 0;

void bfs(ll node, v<ll> &dist, v<ll> &touch) {
  dist[node] = 0;
  queue<ll> q;
  q.push(node);
  while (!q.empty()) {
    auto nd = q.front();
    ll dis = dist[nd];
    q.pop();
    for (auto it : g[nd]) {
      if (dist[it] > dis + 1) {
        dist[it] = dis + 1;
        touch[it] = touch[node];
        if (s[it] == 1)
          touch[it] = 1;
        q.push(it);
      }
      // } else if (dist[it] == dis + 1 && touch[it] == 1 && touch[nd] == 0) {
      //   touch[it] = 0;
      //   q.push(it);
      // }
    }
  }
}

void bfs2(ll node, v<ll> &dist) {
  dist[node] = 0;
  queue<ll> q;
  q.push(node);
  while (!q.empty()) {
    auto nd = q.front();
    if (s[nd] == 1)
      continue;
    ll dis = dist[nd];
    q.pop();
    for (auto it : g[nd]) {
      if (dist[it] > dis + 1) {
        dist[it] = dis + 1;
        q.push(it);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  g.resize(n);
  loc.resize(k);
  s.resize(n);
  lp(i, 0, m) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  string s1;
  cin >> s1;
  ll point = 0;
  lp(i, 0, n) {
    s[i] = (s1[i] == '1');
    if (s[i] == 1) {
      stop_cnt++;
      point = i;
    }
  }

  lp(i, 0, k) {
    cin >> loc[i];
    loc[i]--;
  }

  v<ll> dis(n, 1e18), touch(n, 0), nn(n, 0);

  bfs(loc[0], dis, touch);
  v<ll> dis_from_stp(n, 1e18);
  bfs(loc[point], dis_from_stp, nn);

  v<ll> dis3(n, 1e18);

  bfs2(loc[0], dis3);
  ll sumi = 0;
  lp(i, 1, n) { sumi += dis_from_stp[i]; }
  lp(i, 0, n) {
    ll op1 = dis[i];
    ll tch = touch[i];
    ll ans = 1e18;
    if (tch) {
      ans = dis[i] + sumi;
    } else {
      ans = dis[i];
    }
    ans = min(ans, dis3[i]);
    cout << ans << '\n';
    // ll op1 = cout << dis[i] << '\n';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...