Submission #1167715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167715		jiahng	Board Game (JOI24_boardgame)	C++20	100 / 100	3823 ms	89532 KiB

Main

#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;
	vi costs; // cost to waste i moves
	FOR(m,0,N){
		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){
		int dist5[N+1]; // min turns to get to each node
		mem(dist5, -1);
		deque <int> dq;
		dist5[X[1]] = 0;
		dq.pb(X[1]);

		while (!dq.empty()){
			int cur = dq.front(); dq.pop_front();
			aFOR(i, adj[cur]){
				int w = (A[cur] > 0 && cur != X[1]);
				if (dist5[i] == -1 || dist5[cur] + w < dist5[i]){
					dist5[i] = dist5[cur] + w;
					if (w == 1) dq.pb(i);
					else dq.push_front(i);
				}	
			}	
		}
		//~ FOR(i,1,N) cout << dist5[i] << ' ';
		//~ cout << '\n';
		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 - dist5[i] > Y) continue;
				if (dist4[n.f][n.s-dist5[i]] == -1){
					dist4[n.f][n.s-dist5[i]] = dist4[cur.f][cur.s-dist5[cur.f]] + 1;
					q2.push(n);
				}
			}
		}
		FOR(m,0,Y){
			FOR(i,1,N) if (dist4[i][m] != -1){
				ans[i] = min(ans[i], costs[m+dist5[i]] + 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 (i > 1 && 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(u, adj[cur.s.f]) if (dist3[u][j] == -1 || dist3[u][j] > cur.f + c){
					dist3[u][j] = cur.f + c;
					pq.push(ipi(dist3[u][j], pi(u,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();
}
	

• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 9 / 9
• Subtask 7: 23 / 23
• Subtask 8: 9 / 9