#include <bits/stdc++.h>
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 5e4+5, M = 305;
vector<int> adj[N];
int loc[N], stop[N], stops = 0;
long long dist[N][M], dist2[N][M], sto[M], doub[N], sing[N], ans2[N], dist3[N][2], gh[N], inc[N];
bitset<M> vis[N], visd;
int main()
{
fastio;
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
string s;
cin >> s;
vector<int> st;
for(int i = 1; i <= n; i++)
{
stop[i] = (s[i-1] == '1');
stops += stop[i];
if(stop[i]) st.push_back(i);
}
for(int i = 0; i < k; i++)
{
cin >> loc[i];
}
if(n/k < M-5)
{
memset(dist, 0x3f, sizeof(dist));
memset(dist2, 0x3f, sizeof(dist2));
stops = min(stops, M-5);
queue<int> q[stops+3];
q[0].push(loc[0]);
dist[loc[0]][0] = 0;
vis[loc[0]][0] = true;
for(int i = 0; i <= stops+2; i++)
{
int its = 0;
while(q[i].size())
{
int u = q[i].front();
q[i].pop();
vis[u][i] = false;
int newOg = i;
if(stop[u] && (its || i))
{
newOg++;
}
if(newOg > stops+2) continue;
for(auto it : adj[u])
{
if(dist[it][newOg] > dist[u][i]+1)
{
if(!vis[it][newOg]) q[newOg].push(it);
vis[it][newOg] = true;
dist[it][newOg] = dist[u][i]+1;
}
}
its++;
}
}
for(int i = 1; i <= n; i++) vis[i] = 0, dist2[i][0] = 0;
for(auto it : st) q[0].push(it), vis[it][0] = true;
for(int i = 0; i <= stops+2; i++)
{
while(q[i].size())
{
int u = q[i].front();
q[i].pop();
vis[u][i] = false;
int newOg = i;
if(stop[u])
{
newOg++;
}
if(newOg > stops+2) continue;
for(auto it : adj[u])
{
if(dist2[it][newOg] > dist2[u][i]+1)
{
if(!vis[it][newOg]) q[newOg].push(it);
vis[it][newOg] = true;
dist2[it][newOg] = dist2[u][i]+1;
}
}
}
}
for(int i = 1; i < k; i++)
{
for(int j = 0; j <= stops+2; j++)
{
if(dist2[loc[i]][j] > 1e18)
{
sto[j] = -1;
break;
}
sto[j] += dist2[loc[i]][j];
}
}
for(int i = 1; i <= n; i++)
{
long long ans = dist[i][0];
for(int j = 1; j <= stops+2; j++)
{
if(sto[j] == -1) continue;
ans = min(ans, dist[i][j]+sto[j]);
}
cout << ans << '\n';
}
return 0;
}
memset(sing, 0x3f, sizeof(sing));
memset(doub, 0x3f, sizeof(doub));
queue<int> q;
for(auto it : st)
{
q.push(it);
visd[it] = true;
sing[it] = 0;
}
while(q.size())
{
int u = q.front();
q.pop();
for(auto it : adj[u])
{
if(visd[it]) continue;
sing[it] = sing[u]+1;
q.push(it);
visd[it] = true;
}
}
for(int i = 1; i <= n; i++)
{
sing[i] = 2*(!sing[i])+sing[i];
}
for(int i = 1; i < k; i++) gh[0] += sing[loc[i]];
deque<int> dq;
visd = 0;
for(auto it : st)
{
for(auto it2 : adj[it])
{
if(stop[it2])
{
dq.push_back(it);
visd[it] = true;
doub[it] = 0;
break;
}
}
}
while(dq.size())
{
int u = dq.front();
dq.pop_front();
for(auto it : adj[u])
{
if(doub[it] > doub[u]+(!stop[u]))
{
doub[it] = doub[u]+(!stop[u]);
if(stop[u]) dq.push_front(it);
else dq.push_back(it);
}
}
}
for(int i = 1; i < k; i++)
{
inc[i] = doub[loc[i]]-sing[loc[i]];
}
sort(inc+1, inc+k);
for(int i = 1; i < k; i++)
{
gh[i] = gh[i-1]+inc[i];
}
memset(ans2, 0x3f, sizeof(ans2));
visd = 0;
visd[loc[0]] = 1;
ans2[loc[0]] = 0;
q.push(loc[0]);
while(q.size())
{
int u = q.front();
q.pop();
if(stop[u] && u != loc[0]) continue;
for(auto it : adj[u])
{
if(visd[it]) continue;
q.push(it);
ans2[it] = ans2[u]+1;
visd[it] = true;
}
}
for(int its = 0; its < k; its++)
{
memset(dist3, 0x3f, sizeof(dist3));
dist3[loc[0]][0] = 0;
vis[loc[0]][0] = true;
priority_queue<array<lg, 3>> pq;
pq.push({0, loc[0], 0});
while(pq.size())
{
int u = pq.top()[1];
int ty = pq.top()[2];
vis[u][ty] = 0;
int stopp = (u != loc[0] && stop[u]);
int newty = (ty||stopp);
pq.pop();
for(auto it : adj[u])
{
if(dist3[it][newty] > dist3[u][ty]+(stopp ? 2*(k-1-its)+its+1 : 1))
{
dist3[it][newty] = dist3[u][ty]+(stopp ? 2*(k-1-its)+its+1 : 1);
if(!vis[it][newty])
{
pq.push({-dist3[it][newty], it, newty});
}
vis[it][newty] = true;
}
}
}
for(int i = 1; i <= n; i++)
{
ans2[i] = min(ans2[i], dist3[i][1]+gh[its]-2*(k-1-its));
}
}
for(int i = 1; i <= n; i++) cout << ans2[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
240976 KB |
Output is correct |
| 2 |
Correct |
107 ms |
243028 KB |
Output is correct |
| 3 |
Correct |
118 ms |
244592 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
12112 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
240936 KB |
Output is correct |
| 2 |
Correct |
121 ms |
243024 KB |
Output is correct |
| 3 |
Incorrect |
33 ms |
12116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
240876 KB |
Output is correct |
| 2 |
Correct |
122 ms |
243028 KB |
Output is correct |
| 3 |
Correct |
137 ms |
244560 KB |
Output is correct |
| 4 |
Correct |
141 ms |
244732 KB |
Output is correct |
| 5 |
Correct |
145 ms |
244756 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
11504 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
240976 KB |
Output is correct |
| 2 |
Correct |
107 ms |
243028 KB |
Output is correct |
| 3 |
Correct |
118 ms |
244592 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
12112 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
