Submission #1167696

#TimeUsernameProblemLanguageResultExecution timeMemory
1167696jiahngBoard Game (JOI24_boardgame)C++20
17 / 100
331 ms68136 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][2],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] > 0){ aFOR(j, adj[i]) if (A[j] > 0) A[i] = 2; } mem(dist1,-1); mem(dist2,-1); // get distances to stop cell queue <int> q; FOR(i,1,N) if (A[i] > 0){ 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) priority_queue <pi, vector <pi>, greater <pi> > pq; FOR(i,1,N) if (A[i] == 2){ pq.push(pi(0,i)); dist2[i] = 0; } while (!pq.empty()){ pi cur = pq.top(); pq.pop(); if (dist2[cur.s] != cur.f) continue; aFOR(i, adj[cur.s]) if (dist2[i] == -1 || dist2[i] > cur.f + (A[cur.s]==0)){ dist2[i] = cur.f + (A[cur.s] == 0); pq.push(pi(dist2[i], i)); } } FOR(i,1,N) ans[i] = INF; int Y = N/(K-1)+1; vi costs; // cost to waste i moves FOR(m,0,Y){ int res = 0; if (m > 0){ if (dist1[1] == -1) break; 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; } } costs.pb(res); } if (K > 300){ ans[X[1]] = 0; int Y = N/(K-1)+1; int dist4[N+1][Y+1]; FOR(i,1,N) FOR(j,0,Y) dist4[i][j] = -1; dist4[X[1]][0] = 0; queue <pi> q2; q2.push(pi(X[1], 0)); while (!q2.empty()){ pi cur = q2.front(); q2.pop(); aFOR(i, adj[cur.f]){ pi n = pi(i, cur.s + (cur.f != X[1] && A[cur.f] > 0)); if (n.s > Y) continue; if (dist4[n.f][n.s] == -1){ dist4[n.f][n.s] = dist4[cur.f][cur.s] + 1; q2.push(n); } } } FOR(m,0,Y){ FOR(i,1,N) if (dist4[i][m] != -1){ ans[i] = min(ans[i], costs[m] + dist4[i][m]); } } }else{ queue <int> q; q.push(X[1]); ans[X[1]] = 0; while (!q.empty()){ int cur = q.front(); q.pop(); aFOR(i, adj[cur]) if (ans[i] == INF){ ans[i] = ans[cur] + 1; if (A[i] == 0) q.push(i); } } FOR(i,1,costs.size()-2){ if (costs[i] - costs[i-1] == costs[i+1] - costs[i]) continue; int g = costs[i+1] - costs[i]; priority_queue <ipi, vector <ipi>, greater <ipi> > pq; pq.push(ipi(0,pi(X[1],0))); mem(dist3, -1); dist3[X[1]][0] = 0; while (!pq.empty()){ ipi cur = pq.top(); pq.pop(); if (dist3[cur.s.f][cur.s.s] != cur.f) continue; int c = (A[cur.s.f] > 0 && cur.s.f != X[1] ? g + 1 : 1); int j = cur.s.s||(cur.s.f != X[1] && A[cur.s.f]>0); aFOR(i, adj[cur.s.f]) if (dist3[i][j] == -1 || dist3[i][j] > cur.f + c){ dist3[i][j] = cur.f + c; pq.push(ipi(dist3[i][j], pi(i,j))); } } FOR(j,1,N) if (dist3[j][1] != -1){ ans[j] = min(ans[j], dist3[j][1] + costs[i] - i*g); } } } //~ cout << '\n'; FOR(i,1,N){ //~ assert(ans[i] < INF); //~ assert(ans[i] >= 0); 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...