Submission #501393

#	Time	Username	Problem	Language	Result	Execution time	Memory
501393		IOI_champion_in_1980	Evacuation plan (IZhO18_plan)	C++14	0 / 100	4010 ms	17016 KiB

plan

#include <bits/stdc++.h>
#include <math.h>
typedef long long ll;
using namespace std;
ll i, j, t, a, n, m, b, c, d, f, g, k, mmin;
int x[100010], dis[100010];
vector <vector<pair<int, int>>> vc(100010);
bool npp[100010], vis[100010], wis[100010];
queue<int> q;
set<int> s;
void mintap(int ind, int val)
{
	if (vis[ind]) return;
	vis[ind]=true;
	s.insert(ind);
	if (npp[ind])
	{
		mmin=val;
		return;
	}
	if (x[ind]!=0)
	{
		if (x[ind]+val<mmin) mmin=x[ind]+val;
		return;
	}
	for (int i=0; i<vc[ind].size(); i++)
	{
		int r=val+vc[ind][i].second;
		if (r<mmin) mintap(vc[ind][i].first, r);
	}
}
int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>n>>m;
	for (a=1; a<=m; a++)
	{
		cin>>c>>d>>g;
		vc[c].push_back(make_pair(d, g));
		vc[d].push_back(make_pair(c, g));
	}
//	for (a=1; a<=n; a++)
//	{
//		cout<<a<<": ";
//		for (b=0; b<vc[a].size(); b++)
//		{
//			cout<<" { "<<vc[a][b].first<<" , "<<vc[a][b].second<<" } ";
//		}
//		cout<<endl;
//	}
	cin>>k;
	for (a=1; a<=k; a++)
	{
		cin>>c;
		x[c]=0;
		npp[c]=1;
	}
	for (a=1; a<=n; a++)
	{
		if (npp[a]) continue;
		mmin=INT_MAX;
		for (auto b:s) vis[b]=0;
		s.clear();
		mintap(a, 0);
		x[a]=mmin;
	}
//	for (a=1; a<=n; a++) cout<<a<<") "<<x[a]<<endl;
	cin>>t;
	for (a=1; a<=t; a++)
	{
		cin>>c>>d;
		int ans=INT_MIN;
		for (b=1; b<=n; b++)
		{
			dis[b]=INT_MAX;
			wis[b]=0;
		}
		dis[c] = x[c];
		wis[c] = true;
		q.push(c);
		while (!q.empty())
		{
			int ss = q.front(); 
			q.pop();
			for (auto u : vc[ss]) 
			{
				int p=u.first;
				if (wis[p]) continue;
				if (p!=d)
				{
					wis[p]=true;
					dis[p] = min(x[p], dis[ss]);
					q.push(p);	
					continue;
				}
				else
				{
//					cout<<min(dis[ss], x[d])<<" ";
					ans=max(ans, min(dis[ss], x[d]));	
				}
			}
		}
		cout<<min(ans, min(x[c], x[d]))<<endl;
	}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
*/

Compilation message (stderr)

plan.cpp: In function 'void mintap(int, int)':
plan.cpp:26: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]
   26 |  for (int i=0; i<vc[ind].size(); i++)
      |                ~^~~~~~~~~~~~~~~

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