#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++)
{
if(inc[i] >= 1e18)
{
k = i;
break;
}
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 |
768 ms |
9544 KB |
Output is correct |
| 2 |
Incorrect |
1609 ms |
10972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
768 ms |
9544 KB |
Output is correct |
| 2 |
Incorrect |
1609 ms |
10972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
