Submission #92395

#	Time	Username	Problem	Language	Result	Execution time	Memory
92395		emil_physmath	Evacuation plan (IZhO18_plan)	C++17	29 / 100	4073 ms	22736 KiB

plan

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using std::cout;
using std::cin;
using std::make_pair;
using std::min;
using std::max;
using std::pair;
using std::vector;
const int INF=1000000000;
const int MAXN=100005;
 
vector<pair<int, int> > nei[MAXN];
int dist[MAXN], p[MAXN], val[MAXN], ans[MAXN];
bool used[MAXN];
int parent[MAXN], rank[MAXN];
void make_set (int v);
int find_set (int v);
void union_sets (int a, int b);
void SolveAll(int n, int Q);
void dijkstra(int n, std::priority_queue<pair<int, int> >);
bool dfs(int u, int e, int mindang);
int main()
{
	int n, m, k, Q;
	cin>>n>>m;
	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));
	}
	std::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));
	}
	dijkstra(n, q);
	cin>>Q;
	SolveAll(n, Q);
 
	char I;
	cin >> I;
	return 0;
}

void SolveAll(int n, int Q)
{
	vector<int> dangers;
	for (int u=1; u<=n; u++) dangers.push_back(u);
	std::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;
	vector<pair<pair<int, int>, int> > q;
	for (int i=0; i<Q; i++)
	{
		int s, e;
		scanf("%d%d", &s, &e);
		q.push_back(make_pair(make_pair(s, e), i));
		ans[q.size()-1]=-1;
	}
	std::sort(q.begin(), q.end(),
		[] (const pair<pair<int, int>, int> & a, const pair<pair<int, int>, int> & b) {
			return max(dist[a.first.first], dist[a.first.second])>
				max(dist[b.first.first], dist[b.first.second]);
	});
	for (int u=1; u<=n; u++) make_set(u);
	int ql=0;
	for (int j=0; j<dangers.size(); j++)
	{
		int curNode=dangers[j];
		for (int i=0; i<nei[curNode].size(); i++)
			if (dist[nei[curNode][i].first]>=dist[curNode])
				union_sets(curNode, nei[curNode][i].first);
		if (j+1<dangers.size() && dist[dangers[j+1]]==dist[dangers[j]]) continue;
		for (int i=ql; i<q.size(); i++)
		{
			if (max(dist[q[i].first.first],
				dist[q[i].first.second])<dist[curNode]) break;
			if (ans[q[i].second]==-1 && find_set(q[i].first.first)==find_set(q[i].first.second))
				ans[q[i].second]=dist[curNode];
			if (ans[q[i].second]!=-1 && q[i].second==ql)
				ql++;
		}
	}
	for (int i=0; i<q.size(); i++)
		cout<<ans[i]<<'\n';
}

void dijkstra(int n, std::priority_queue<pair<int, int> > q)
{
	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));
			}
		}
	}
}

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;
}

void make_set (int v) {
	parent[v] = v;
	rank[v] = 0;
}

int find_set (int v) {
	if (v == parent[v])
		return v;
	return parent[v] = find_set (parent[v]);
}

void union_sets (int a, int b) {
	a = find_set (a);
	b = find_set (b);
	if (a != b) {
		if (rank[a] < rank[b])
			std::swap (a, b);
		parent[b] = a;
		if (rank[a] == rank[b])
			++rank[a];
	}
}

Compilation message (stderr)

plan.cpp: In function 'void SolveAll(int, int)':
plan.cpp:66:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<dangers.size(); i++)
                ~^~~~~~~~~~~~~~~
plan.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j=0; j<dangers.size(); j++)
                ~^~~~~~~~~~~~~~~
plan.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<nei[curNode].size(); i++)
                 ~^~~~~~~~~~~~~~~~~~~~
plan.cpp:89:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (j+1<dangers.size() && dist[dangers[j+1]]==dist[dangers[j]]) continue;
       ~~~^~~~~~~~~~~~~~~
plan.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=ql; i<q.size(); i++)
                  ~^~~~~~~~~
plan.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<q.size(); i++)
                ~^~~~~~~~~
plan.cpp: In function 'void dijkstra(int, std::priority_queue<std::pair<int, int> >)':
plan.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<nei[v].size(); j++)
                 ~^~~~~~~~~~~~~~
plan.cpp: In function 'bool dfs(int, int, int)':
plan.cpp:133: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:33: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:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
plan.cpp: In function 'void SolveAll(int, int)':
plan.cpp:72: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: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46