#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf = 1e18;
const ll mod2 = 1e9 + 7;
const int mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
if(x+y>=mod2) x-=mod2;
if(x+y<0)x+=mod2;
return x+y;
}
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a, b, c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,t,lim,w,l,r ;
int kk;
int el = 19;
main()
{
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
NHP
/// cin>>s1;
// modwwe
phongbeo();
// checktime
}
string s;
vector<int> v[50001];
int ans[50001];
int c[50001];
int d[50001];
int cost[50001];
int vis[50001];
int a[50001];
vector<int> cd;
struct cmp
{
bool operator()(id a,id b)
{
return a.a>b.a;
}
};
priority_queue<id,vector<id>,cmp>p;
void bfs(int c[],bool k)
{
deque<ib>q;
for(int i=1; i<=n; i++)
if(s[i-1]=='1')
{
if(k)
{
for(auto f:v[i])
if(s[f-1]=='1')
{
q.pb({0,i});
}
}
else
{
q.pb({0,i});
}
}
while(!q.empty())
{
ib x=q.front();
q.pop_front();
if(vis[x.b]) continue;
vis[x.b]=1;
for(auto f:v[x.b])
{
c[f]=min(x.a+1,c[f]);
if(s[f-1]=='1')q.push_front({x.a,f});
else q.push_back({x.a+1,f});
}
}
}
namespace k_low
{
bool cc[50001][201];
void solve()
{
sort(cd.begin(),cd.end());
int total=0;
for(int i=0; i<k; i++)
{
p.push({total+s4,s9,i,0});
cost[i]=i+(k-i-1)*2;
total+=cd[i];
}
while(!p.empty())
{
id x=p.top();
p.pop();
if(cc[x.b][x.c]) continue;
cc[x.b][x.c]=1;
if(x.d)
{
ans[x.b]=min(ans[x.b],x.a);
}
for(auto f:v[x.b])
if(s[f-1]=='1')
{
if(x.d)
ans[f]=min(ans[f],x.a+1);
p.push({x.a+cost[x.c]+1,f,x.c,1});
}
else
{
p.push({x.a+1,f,x.c,x.d});
}
}
}
};
namespace k_high{
int pre[50001];
int cur[50001];
int min_cost[50001];
bool cc[50001][225];
void solve()
{
for(int i=2;i<=k;i++)
{
l=a[i];
int ci=c[l];
int di=d[l];
if(c[l]==0) c[l]+=2;
if(d[l]==0) d[l]=1;
c[l]-=2;
d[l]--;
s3=d[l]-c[l];
pre[s3]+=d[l];
pre[s3]-=c[l];
pre[1]+=c[l];
cur[s3]++;
cur[s3]-=2;
cur[1]+=2;
pre[s3]-=(s3-1);
c[l]=ci;
d[l]=di;
}
for(int i=1;i<=n;i++)
cur[i]+=cur[i-1],
pre[i]+=pre[i-1]+cur[i],
min_cost[i]=-1;
deque<ic> q;
q.push_front({0,s9});
memset(vis,-1,sizeof vis);
while(!q.empty())
{
ic x=q.front();
q.pop_front();
if(vis[x.b]!=-1) continue;
vis[x.b]=x.a;
for(auto f:v[x.b])
if(s[f-1]=='1') q.pb({x.a+1,f});
else q.push_front({x.a,f});
}
q.pb({0,s9,0});
while(!q.empty())
{
ic x=q.front();
q.pop_front();
if((x.c-vis[x.b])*(k-1)>=n) continue;
if(cc[x.b][x.c-vis[x.b]]) continue;
cc[x.b][x.c-vis[x.b]]=1;
if(s[x.b-1]=='1')s4=1;
else s4=0;
ans[x.b]=min(ans[x.b],x.a+pre[x.c-s4]);
for(auto f:v[x.b])
if(s[f-1]=='1')
q.pb({x.a+1,f,x.c+1});
else q.pb({x.a+1,f,x.c});
}
memset(vis,0,sizeof vis);
}
};
void phongbeo()
{
cin>>n>>m>>k;
for(int i=1; i<=m; i++)
cin>>l>>r,v[l].pb(r),v[r].pb(l);
cin>>s;
for(int i=1; i<=n; i++)
d[i]=inf,c[i]=inf;
bfs(c,0);
memset(vis,0,sizeof vis);
bfs(d,1);
memset(vis,0,sizeof vis);
for(int i=1; i<=k; i++)
{
cin>>l;
int ci=c[l];
int di=d[l];
if(c[l]==0) c[l]+=2;
if(d[l]==0) d[l]=1;
if(i==1)s9=l;
else c[l]-=2,d[l]--,cd.pb(d[l]-c[l]),s4+=c[l];
a[i]=l;
c[l]=ci;
d[l]=di;
}
for(int i=1; i<=n; i++)
ans[i]=inf;
if(k<=0)
{
k_low::solve();
}
else
{
k_high::solve();
}
p.push({0,s9,0,0});
ans[s9]=0;
while(!p.empty())
{
id x=p.top();
p.pop();
if(vis[x.b]) continue;
vis[x.b]=1;
for(auto f:v[x.b])
{
ans[f]=min(ans[f],x.a+1);
if(s[f-1]=='0') p.push({x.a+1,f,x.c,x.d});
}
}
for(int i=1; i<=n; i++)
cout<<ans[i]<<" ";
}
Compilation message
Main.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
75 | main()
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define fin(x) freopen(x".inp","r",stdin)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:79:9: note: in expansion of macro 'fin'
79 | fin(task);
| ^~~
Main.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | #define fou(x) freopen(x".out","w",stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:80:9: note: in expansion of macro 'fou'
80 | fou(task);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8016 KB |
Output is correct |
| 2 |
Correct |
27 ms |
15640 KB |
Output is correct |
| 3 |
Correct |
66 ms |
20808 KB |
Output is correct |
| 4 |
Correct |
54 ms |
19928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
10832 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10576 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
14456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
14456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
10716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8016 KB |
Output is correct |
| 2 |
Correct |
27 ms |
15640 KB |
Output is correct |
| 3 |
Correct |
66 ms |
20808 KB |
Output is correct |
| 4 |
Correct |
54 ms |
19928 KB |
Output is correct |
| 5 |
Runtime error |
14 ms |
10832 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
