#include <bits/stdc++.h>
using namespace std;
using graph = vector<vector<int>>;
using lli = long long;
tuple<lli, int, vector<int>> calc_slopes(graph &G, vector<bool> &red, vector<int> &frens) {
int n = G.size();
vector<int> dist2(n, -1);
{
queue<int> q;
for (int i = 0; i < n; ++i) if (red[i]) {
q.push(i);
dist2[i] = 0;
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v: G[u]) if (dist2[v] == -1) {
dist2[v] = dist2[u] + 1;
q.push(v);
}
}
}
vector<int> dist1(n, -1);
{
deque<int> q;
for (int i = 0; i < n; ++i) if (red[i]) {
bool ok = false;
for (int v: G[i]) if (red[v])
ok = true;
if (ok) {
dist1[i] = 0;
q.push_back(i);
}
}
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (int v: G[u]) if (dist1[v] > dist1[u] + !red[u] || dist1[v] == -1)
if (red[u]) { dist1[v] = dist1[u]; q.push_front(v); }
else { dist1[v] = dist1[u] + 1; q.push_back(v); }
}
}
lli c0 = 0;
vector<int> slopes; int sl = 0;
for (int f: frens) {
if (dist2[f] == 0) dist2[f] = (dist1[f] == 0 ? 1 : 2);
c0 += dist2[f];
++sl;
// cerr << f << " -> " << dist1[f] << " " << dist2[f] << "\n";
if (dist1[f] != -1 && dist1[f] - dist2[f] + 2 > 1) {
slopes.push_back(dist1[f] - dist2[f] + 2);
++sl;
}
if (dist1[f] == -1) ++sl;
}
// cerr << c0 << " " << sl << "\n";
sort(slopes.begin(), slopes.end());
return {c0, sl, slopes};
}
vector<vector<int>> calc_dists(graph &G, int s, vector<bool> &red, int mx) {
int n = G.size();
vector<vector<int>> dist(n, vector<int>(mx, -1));
queue<pair<int, int>> q;
q.emplace(s, 0);
dist[s][0] = 0;
while (!q.empty()) {
auto [u, k] = q.front(); q.pop();
for (int v: G[u]) if (k + red[v] < mx && dist[v][k + red[v]] == -1) {
q.emplace(v, k + red[v]);
dist[v][k + red[v]] = dist[u][k] + 1;
}
}
return dist;
}
vector<lli> calc_dists2(graph &G, int st, vector<bool> &red, int a) {
int n = G.size();
vector<vector<lli>> dist(n, vector<lli>(2, 1e18));
set<tuple<lli, int, int>> s;
s.emplace(dist[st][0] = 0, st, 0);
vector<vector<bool>> marc(n, vector<bool>(2));
while (!s.empty()) {
auto [d, u, b] = *s.begin(); s.erase(s.begin());
if (marc[u][b]) continue;
marc[u][b] = true;
int k = 1 + (u != st ? a*red[u] : 0);
int nb = b || (u != st ? red[u] : false);
for (int v: G[u]) if (dist[v][nb] > d + k)
s.emplace(dist[v][nb] = d + k, v, nb);
}
vector<lli> ans(n);
for (int i = 0; i < n; ++i)
ans[i] = dist[i][1];
return ans;
}
vector<int> calc_mn(graph &G, int s, vector<bool> &red) {
int n = G.size();
vector<int> dist(n, -1);
deque<int> q;
q.push_back(s);
dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (int v: G[u]) if (dist[v] == -1 || dist[v] > dist[u] + red[v])
if (red[v]) { dist[v] = dist[u] + 1; q.push_back(v); }
else { dist[v] = dist[u]; q.push_front(v); }
}
return dist;
}
vector<vector<int>> calc_dists3(graph &G, int s, vector<bool> &red, vector<int> &mn, int mx) {
int n = G.size();
vector<vector<int>> dist(n, vector<int>(mx, -1));
queue<pair<int, int>> q;
q.emplace(s, 0);
dist[s][0] = 0;
while (!q.empty()) {
auto [u, k] = q.front(); q.pop();
for (int v: G[u]) {
int d = k + red[v] - mn[v] + mn[u];
if (d < mx && dist[v][d] == -1) {
q.emplace(v, d);
dist[v][d] = dist[u][k] + 1;
}
}
}
return dist;
}
int main() {
int n, m, p;
cin >> n >> m >> p;
graph G(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<bool> red(n); bool ok = false;
for (int i = 0; i < n; ++i) {
char c;
cin >> c; red[i] = c - '0';
ok = ok || red[i];
}
int s;
cin >> s;
--s;
if (!ok) {
vector<vector<int>> dist = calc_dists(G, s, red, 1);
for (int i = 0; i < n; ++i)
cout << dist[i][0] << " ";
cout << "\n";
return 0;
}
--p;
vector<int> frens(p);
for (int &f: frens) {
cin >> f;
--f;
}
auto [c0, sl, slopes] = calc_slopes(G, red, frens);
vector<lli> ans(n, 1e18);
{
vector<vector<int>> dist = calc_dists(G, s, red, 2);
for (int u = 0; u < n; ++u)
if (!red[u] && dist[u][0] != -1)
ans[u] = min(ans[u], 1LL*dist[u][0]);
else if (red[u] && dist[u][1] != -1)
ans[u] = min(ans[u], 1LL*dist[u][1]);
ans[s] = 0;
}
if (true) {
int mx = n/p + 5;
vector<int> mn = calc_mn(G, s, red);
vector<vector<int>> dist = calc_dists3(G, s, red, mn, mx);
vector<lli> costs(n);
int j = 0; int cur = sl; lli c = c0;
for (int i = 1; i < n; ++i) {
while (j < slopes.size() && slopes[j] <= i) { ++j; --cur; }
costs[i] = c;
c += cur;
}
for (int u = 0; u < n; ++u) {
for (int i = mn[u] - red[u]; i < min(mn[u] - red[u] + mx, n); ++i)
if (!red[u] && dist[u][i - mn[u]] != -1)
ans[u] = min(ans[u], costs[i] + dist[u][i - mn[u]]);
else if (red[u] && i + 1 - mn[u] < mx && dist[u][i + 1 - mn[u]] != -1)
ans[u] = min(ans[u], costs[i] + dist[u][i + 1 - mn[u]]);
}
}
else {
{
vector<lli> dist = calc_dists2(G, s, red, sl);
for (int u = 0; u < n; ++u) {
// cerr << c0 - sl + dist[u] << "\n";
ans[u] = min(ans[u], c0 - sl + dist[u]);
}
}
int cur = sl; lli c = c0; int lst = 1;
for (int x: slopes) {
// cerr << x << " cost = " << c << "\n";
c += 1LL*cur*(x - lst);
--cur;
vector<lli> dist = calc_dists2(G, s, red, cur);
for (int u = 0; u < n; ++u)
ans[u] = min(ans[u], c - 1LL*cur*x + dist[u]);
}
}
for (lli x: ans)
cout << x << " ";
cout << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |