Submission #556289

#	Time	Username	Problem	Language	Result	Execution time	Memory
556289		Hanksburger	Evacuation plan (IZhO18_plan)	C++17	0 / 100	411 ms	43124 KiB

plan

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[100005];
priority_queue<pair<int, int> > pq;
int dist[100005], par[100005];
pair<int, int> dp[100005][20];
vector<pair<int, int> > edge;
bool visited[100005];
bool cmp(pair<int, int> x, pair<int, int> y)
{
	return (min(dist[x.first], dist[x.second])>min(dist[y.first], dist[y.second]));
}
int findPar(int u)
{
	if (par[u]==u)
		return u;
	par[u]=findPar(par[u]);
	return par[u];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, p, q;
	cin >> n >> m;
	for (int i=1; i<=m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edge.push_back({u, v});
	}
	cin >> p;
	for (int i=1; i<=n; i++)
		dist[i]=1e9;
	for (int i=1; i<=p; i++)
	{
		int u;
		cin >> u;
		dist[u]=0;
		pq.push({0, u});
	}
	while (!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		if (visited[u])
			continue;
		visited[u]=1;
		for (int i=0; i<adj[u].size(); i++)
		{
			int v=adj[u][i].first, w=adj[u][i].second;
			if (dist[v]>dist[u]+w)
			{
				dist[v]=dist[u]+w;
				pq.push({-dist[v], v});
			}
		}
	}
	sort(edge.begin(), edge.end(), cmp);
	for (int i=1; i<=n; i++)
		par[i]=i;
	for (int i=0; i<edge.size(); i++)
	{
		int u=edge[i].first, v=edge[i].second;
		int paru=findPar(u), parv=findPar(v);
		if (paru!=parv)
		{
			par[paru]=parv;
			if (!dp[paru][0].first)
				dp[paru][0]={parv, min(dist[u], dist[v])};
		}
	}
	for (int i=1; i<=n; i++)
		if (!dp[i][0].first)
			dp[i][0]={i, dist[i]};
	for (int i=1; i<=19; i++)
		for (int j=1; j<=n; j++)
			dp[j][i]={dp[dp[j][i-1].first][i-1].first, dp[dp[j][i-1].first][i-1].second};
	cin >> q;
	for (int i=1; i<=q; i++)
	{
		int u, v, l=0, r=1e9;
		cin >> u >> v;
		while (l<r)
		{
			int mid=(l+r+1)/2, fu=u, fv=v;
			for (int j=19; j>=0; j--)
				if (dp[fu][j].second>=mid)
					fu=dp[fu][j].first;
			for (int j=19; j>=0; j--)
				if (dp[fv][j].second>=mid)
					fv=dp[fv][j].first;
			if (fu==fv)
				l=mid;
			else
				r=mid-1;
		}
		cout << l << '\n';
	}
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i=0; i<adj[u].size(); i++)
      |                 ~^~~~~~~~~~~~~~
plan.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i=0; i<edge.size(); i++)
      |                ~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46