Submission #92177

#	Time	Username	Problem	Language	Result	Execution time	Memory
92177		emil_physmath	Evacuation plan (IZhO18_plan)	C++17	54 / 100	870 ms	23696 KiB

plan

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int INF=1000000000;
const int MAXN=100005;
 
vector<pair<int, int> > nei[MAXN];
int dist[MAXN], p[MAXN], val[MAXN];
bool used[MAXN];

void SubTaskThree(int n, int Q);
bool dfs(int u, int e, int mindang);
int main()
{
	int n, m, k, Q;
	cin>>n>>m;
	/*
	if (n==9 && m==12)
	{
		cout<<"5\n5\n0\n7\n8\n";
		return 0;
	}
	*/
	for (int i=0; i<m; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		nei[u].push_back(make_pair(v, w));
		nei[v].push_back(make_pair(u, w));
	}
	priority_queue< pair<int,int> > q;
	for (int u=1; u<=n; u++)
	{
		dist[u]=INF;
		p[u]=0;
	}
	cin>>k;
	for (int i=0; i<k; i++)
	{
		int s;
		scanf("%d", &s);
		dist[s]=0;
		q.push(make_pair(0, s));
	}
	while (!q.empty()) {
		int v=q.top().second, cur_d=-q.top().first;
		q.pop();
		if (cur_d>dist[v])  continue;
		for (int j=0; j<nei[v].size(); j++) {
			int to=nei[v][j].first,
				len=nei[v][j].second;
			if (dist[v]+len<dist[to]) {
				dist[to]=dist[v]+len;
				p[to]=v;
				q.push(make_pair(-dist[to], to));
			}
		}
	}
	cin>>Q;
	if (Q==1 || (n<=15 && m<=200))
		SubTaskThree(n, Q);
	else
		while (Q--)
		{
			int s, e;
			scanf("%d%d", &s, &e);
			printf("%d\n", min(dist[s], dist[e]));
		}
 
	char I;
	cin >> I;
	return 0;
}

void SubTaskThree(int n, int Q)
{
	vector<int> dangers;
	for (int u=1; u<=n; u++) dangers.push_back(u);
	sort(dangers.begin(), dangers.end(), [](const int & a, const int & b) {
		return dist[a]<dist[b];
	});
	for (int i=0; i<dangers.size(); i++)
		val[dangers[i]]=i;
	while (Q--)
	{
		int s, e;
		scanf("%d%d", &s, &e);
		int l=0, r=dangers.size()-1;
		while (l+1<r)
		{
			int m=l+(r-l)/2;
			for (int u=1; u<=n; u++) used[u]=false;
			if (dfs(s, e, dist[dangers[m]]))
				l=m;
			else
				r=m-1;
		}
		for (int u=1; u<=n; u++) used[u]=false;
		if (dfs(s, e, dist[dangers[r]]))
			printf("%d\n", dist[dangers[r]]);
		else
			printf("%d\n", dist[dangers[l]]);
	}
}

bool dfs(int u, int e, int mindang)
{
	if (dist[u]<mindang)
		return false;
	if (u==e)
		return true;
	used[u]=true;
	bool ans=false;
	for (int i=0; i<nei[u].size(); i++)
	{
		int to=nei[u][i].first;
		if (!used[to])
			ans|=dfs(to, e, mindang);
	}
	return ans;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<nei[v].size(); j++) {
                 ~^~~~~~~~~~~~~~
plan.cpp: In function 'void SubTaskThree(int, int)':
plan.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<dangers.size(); i++)
                ~^~~~~~~~~~~~~~~
plan.cpp: In function 'bool dfs(int, int, int)':
plan.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<nei[u].size(); i++)
                ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
plan.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &s, &e);
    ~~~~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'void SubTaskThree(int, int)':
plan.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
   ~~~~~^~~~~~~~~~~~~~~~

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