Submission #1167394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167394		jiahng	Board Game (JOI24_boardgame)	C++20	14 / 100	4094 ms	27224 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],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){
		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;
			}
		}
		//~ cout << res << ' ';
		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));
			}
		}
		
		
	}
	//~ cout << '\n';
	FOR(i,1,N) cout << ans[i] << '\n';
	
}
	
	
int32_t main(){
	fast;
	solve();
}
	

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