Submission #1036604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036604		Unforgettablepl	Board Game (JOI24_boardgame)	C++17	17 / 100	50 ms	6868 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e13;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,k;
	cin >> n >> m >> k;
	vector<vector<int>> adj(n+1);
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	vector<bool> isStop(n+1);
	bool works = false;
	for(int i=1;i<=n;i++){
		char a;cin>>a;
		if(a=='1'){works=isStop[i]=true;}
	}
	vector<int> starts(k+1);
	for(int i=1;i<=k;i++)cin>>starts[i];
	vector<int> minmoves(n+1,INF);
	minmoves[0]=0;
	if(works){
		// calculate minmoves
		vector<int> nearest_single(n+1,-1);
		priority_queue<pair<int,int>> pq;
		for(int i=1;i<=n;i++)if(isStop[i])for(int&x:adj[i])pq.emplace(-1,x);
		vector<bool> visited(n+1);
		while(!pq.empty()){
			auto [dist,idx] = pq.top();pq.pop();dist=-dist;
			if(visited[idx])continue;
			visited[idx]=true;
			nearest_single[idx]=dist;
			for(int&i:adj[idx])if(!visited[i])pq.emplace(-dist-1,i);
		}
		vector<int> nearest_double(n+1,-1);
		for(int i=1;i<=n;i++)if(isStop[i]){
			for(int&x:adj[i]){
				if(isStop[x]){
					pq.emplace(0,i);
					break;
				}
			}
		}
		visited = vector<bool>(n+1);
		while(!pq.empty()){
			auto [dist,idx] = pq.top();pq.pop();dist=-dist;
			if(visited[idx])continue;
			visited[idx]=true;
			nearest_double[idx]=dist;
			if(!isStop[idx])nearest_double[idx]--;
			for(int&i:adj[idx])if(!visited[i]){
				if(!isStop[i])pq.emplace(-dist-1,i);
				else pq.emplace(-dist,i);
			}
		}
		vector<int> slopeedit(n+1);
		int base = 0;
		auto process = [&](int x){
			base+=nearest_single[x];
			slopeedit[1]+=2;
			if(nearest_double[1]!=-1 and nearest_double[x]-nearest_single[x]+2<=n)slopeedit[nearest_double[x]-nearest_single[x]+2]--;
		};
		for(int i=2;i<=k;i++){
			process(starts[i]);
		}
		int currslope = 0;
		for(int i=1;i<=n;i++){
			base+=currslope;
			minmoves[i]=base;
			currslope+=slopeedit[i];
		}
		for(int i=n;i;i--)minmoves[i]-=minmoves[i-1];
	}
	vector<int> currbest(n+1,INF);
	vector<int> ans(n+1,INF);
	vector<bool> visited(n+1);
	priority_queue<tuple<int,int,int>> pq;
	pq.emplace(0,0,starts[1]);
	while(!pq.empty()){
		auto [stops,dist,idx] = pq.top();pq.pop();dist=-dist;stops=-stops;
		if(visited[idx])continue;
		if(isStop[idx])currbest[idx] = dist-minmoves[stops];
		else currbest[idx] = dist;
		visited[idx] = true;
		for(int&i:adj[idx]){
			if(isStop[i]){
				if(dist+1+minmoves[stops+1]<currbest[i]){
					currbest[i] = dist+1+minmoves[stops+1];
					pq.emplace(-stops-1,-dist-1-minmoves[stops+1],i);
					visited[i]=false;
				} 
				ans[i]=min(ans[i],dist+1);
			} else {
				if(dist+1<currbest[i]){
					currbest[i] = dist+1;
					pq.emplace(-stops,-dist-1,i);
					visited[i]=false;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<min(currbest[i],ans[i])<<'\n';
}

• Subtask 1: 3 / 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