Submission #989812

#	Time	Username	Problem	Language	Result	Execution time	Memory
989812		Cyber_Wolf	Board Game (JOI24_boardgame)	C++17	0 / 100	1609 ms	11344 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 5e4+5, M = 305;

vector<int> adj[N];
int loc[N], stop[N], stops = 0;
long long dist[N][M], dist2[N][M], sto[M], doub[N], sing[N], ans2[N], dist3[N][2], gh[N], inc[N];
bitset<M> vis[N], visd;

int main()
{
	fastio;
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string s;
	cin >> s;
	vector<int> st;
	for(int i = 1; i <= n; i++)
	{
		stop[i] = (s[i-1] == '1');
		stops += stop[i];
		if(stop[i])	st.push_back(i);
	}
	for(int i = 0; i < k; i++)
	{
		cin >> loc[i];
	}
	// if(n/k < M-5)
	// {
		// memset(dist, 0x3f, sizeof(dist));
		// memset(dist2, 0x3f, sizeof(dist2));
		// stops = min(stops, M-5);
		// queue<int> q[stops+3];
		// q[0].push(loc[0]);
		// dist[loc[0]][0] = 0;
		// vis[loc[0]][0] = true;
		// for(int i = 0; i <= stops+2; i++)
		// {
			// int its = 0;
			// while(q[i].size())
			// {
				// int u = q[i].front();
				// q[i].pop();
				// vis[u][i] = false;
				// int newOg = i;
				// if(stop[u] && (its || i))
				// {
					// newOg++;
				// }
				// if(newOg > stops+2)	continue;
				// for(auto it : adj[u])
				// {
					// if(dist[it][newOg] > dist[u][i]+1)
					// {
						// if(!vis[it][newOg])	q[newOg].push(it);
						// vis[it][newOg] = true;
						// dist[it][newOg] = dist[u][i]+1;	
					// }
				// }
				// its++;
			// }
		// }
		// for(int i = 1; i <= n; i++)	vis[i] = 0, dist2[i][0] = 0;
		// for(auto it : st)	q[0].push(it), vis[it][0] = true;
		// for(int i = 0; i <= stops+2; i++)
		// {
			// while(q[i].size())
			// {
				// int u = q[i].front();
				// q[i].pop();
				// vis[u][i] = false;
				// int newOg = i;
				// if(stop[u])
				// {
					// newOg++;
				// }
				// if(newOg > stops+2)	continue;
				// for(auto it : adj[u])
				// {
					// if(dist2[it][newOg] > dist2[u][i]+1)
					// {
						// if(!vis[it][newOg])	q[newOg].push(it);
						// vis[it][newOg] = true;
						// dist2[it][newOg] = dist2[u][i]+1;	
					// }
				// }
			// }
		// }
		// for(int i = 1; i < k; i++)
		// {
			// for(int j = 0; j <= stops+2; j++)
			// {
				// if(dist2[loc[i]][j] > 1e18)
				// {
					// sto[j] = -1;
					// break;
				// }
				// sto[j] += dist2[loc[i]][j];
			// }
		// }
		// for(int i = 1; i <= n; i++)
		// {
			// long long ans = dist[i][0];
			// for(int j = 1; j <= stops+2; j++)
			// {
				// if(sto[j] == -1)	continue;
				// ans = min(ans, dist[i][j]+sto[j]);
			// }
			// cout << ans << '\n';
		// }
		// return 0;
	// }
	memset(sing, 0x3f, sizeof(sing));
	memset(doub, 0x3f, sizeof(doub));
	queue<int> q;
	for(auto it : st)
	{
		q.push(it);
		visd[it] = true;
		sing[it] = 0;
	}
	while(q.size())
	{
		int u = q.front();
		q.pop();
		for(auto it : adj[u])
		{
			if(visd[it])	continue;
			sing[it] = sing[u]+1;
			q.push(it);
			visd[it] = true;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		sing[i] = 2*(!sing[i])+sing[i];
	}
	for(int i = 1; i < k; i++)	gh[0] += sing[loc[i]];
	deque<int> dq;
	visd = 0;
	for(auto it : st)
	{
		for(auto it2 : adj[it])
		{
			if(stop[it2])
			{
				dq.push_back(it);
				visd[it] = true;
				doub[it] = 0;
				break;
			}
		}
	}
	while(dq.size())
	{
		int u = dq.front();
		dq.pop_front();
		for(auto it : adj[u])
		{
			if(doub[it] > doub[u]+(!stop[u]))
			{
				doub[it] = doub[u]+(!stop[u]);
				if(stop[u])	dq.push_front(it);
				else	dq.push_back(it);	
			}
		}
	}
	for(int i = 1; i < k; i++)
	{
		inc[i] = doub[loc[i]]-sing[loc[i]];
	}
	sort(inc+1, inc+k);
	for(int i = 1; i < k; i++)
	{
		if(inc[i] >= 1e18)	
		{
			k = i;
			break;
		}
		gh[i] = gh[i-1]+inc[i];
	}
	memset(ans2, 0x3f, sizeof(ans2));
	visd = 0;
	visd[loc[0]] = 1;
	ans2[loc[0]] = 0;
	q.push(loc[0]);
	while(q.size())
	{
		int u = q.front();
		q.pop();
		if(stop[u] && u != loc[0])	continue;
		for(auto it : adj[u])
		{
			if(visd[it])	continue;
			q.push(it);
			ans2[it] = ans2[u]+1;
			visd[it] = true;
		}
	}
	for(int its = 0; its < k; its++)
	{
		memset(dist3, 0x3f, sizeof(dist3));
		dist3[loc[0]][0] = 0;
		vis[loc[0]][0] = true;
		priority_queue<array<lg, 3>> pq;
		pq.push({0, loc[0], 0});
		while(pq.size())
		{
			int u = pq.top()[1];
			int ty = pq.top()[2];
			vis[u][ty] = 0;
			int stopp = (u != loc[0] && stop[u]);
			int newty = (ty||stopp);
			pq.pop();
			for(auto it : adj[u])
			{
				if(dist3[it][newty] > dist3[u][ty]+(stopp ? 2*(k-1-its)+its+1 : 1))
				{
					dist3[it][newty] = dist3[u][ty]+(stopp ? 2*(k-1-its)+its+1 : 1);
					if(!vis[it][newty])
					{
						pq.push({-dist3[it][newty], it, newty});
					}
					vis[it][newty] = true;
				}
			}
		}
		for(int i = 1; i <= n; i++)
		{
			ans2[i] = min(ans2[i], dist3[i][1]+gh[its]-2*(k-1-its));
		}
	}
	for(int i = 1; i <= n; i++)	cout << ans2[i] << '\n';
	
	
	

    return 0;
}

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