Submission #1167380

#TimeUsernameProblemLanguageResultExecution timeMemory
1167380jiahngBoard Game (JOI24_boardgame)C++20
17 / 100
32 ms27208 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi,ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0) #define maxn 500010 #define INF int(1e18) #define MOD 1000000007 #define DEBUG 0 typedef pair <int, pi> ipi; typedef pair <pi,pi> pipi; int N,M,K; vi adj[maxn]; int A[maxn], X[maxn]; int dist1[maxn], dist2[maxn], dist3[maxn],ans[maxn]; void solve(){ cin >> N >> M >> K; int a,b; FOR(i,1,M){ cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } string S; cin >> S; FOR(i,1,N) A[i] = (S[i-1] == '1'); FOR(i,1,K) cin >> X[i]; FOR(i,1,N) if (A[i]){ aFOR(j, adj[i]) if (A[j]) A[i] = 2; } mem(dist1,-1); mem(dist2,-1); // get distances to stop cell queue <int> q; FOR(i,1,N) if (A[i]){ q.push(i); dist1[i] = 0; } while (!q.empty()){ int cur = q.front(); q.pop(); aFOR(i, adj[cur]) if (dist1[i] == -1){ dist1[i] = dist1[cur] + 1; q.push(i); } } // get distances to stop cell pairs (dist - turn no) deque <int> dq; FOR(i,1,N) if (A[i] == 2){ dq.pb(i); dist2[i] = 0; } while (!dq.empty()){ int cur = dq.front(); dq.pop_front(); aFOR(i, adj[cur]) if (dist2[i] == -1){ dist2[i] = dist2[cur] + (A[cur] == 0 && A[i] != 2); if (A[cur] == 0 && A[i] != 2) dq.push_back(i); else dq.push_front(i); } } priority_queue <pi, vector <pi>, greater <pi> > pq; vpi v; mem(dist3,-1); FOR(i,1,N) ans[i] = INF; pq.push(pi(0,X[1])); dist3[X[1]] = 0; ans[X[1]] = 0; FOR(m,0,N/(K-1)+10){ int res = 0; if (m > 0){ FOR(i,2,K){ int x = X[i]; int val; if (dist1[x] == 0){ if (dist2[x] == -1) val = 2*m; else val = min(2*m, m + dist2[x]); }else{ if (dist2[x] == -1) val = dist1[x] + 2*(m-1); else val = min(dist1[x] + 2*(m-1), m + dist2[x]); } res += val; } } aFOR(i, v) pq.push(i); v.clear(); while (!pq.empty()){ pi cur = pq.top(); pq.pop(); if (dist3[cur.s] != cur.f) continue; aFOR(i, adj[cur.s]) if (dist3[i] == -1 || dist3[i] > cur.f + 1){ dist3[i] = cur.f + 1; ans[i] = min(ans[i], res + dist3[i]); if (A[i]) v.pb(pi(dist3[i], i)); else pq.push(pi(dist3[i], i)); } } } FOR(i,1,N) cout << ans[i] << '\n'; } int32_t main(){ fast; solve(); }
#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...