Submission #90567

#	Time	Username	Problem	Language	Result	Execution time	Memory
90567		Abelyan	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1727 ms	44132 KiB

plan

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
 
struct street
{
	int to;
	int d;
};
 
bool operator<(street a, street b)
{
	return a.d > b.d;
}
 
int n, m, k, used[100005], d[100005];
vector<street> gr[100005];
priority_queue<street> q;
 
 
int p[100005],timer,tin[100005],tout[100005],up[100005][20],mn[100005][20];
vector<pair<int, int>> st;
vector<int> g[100005];
int getParent(int k)
{
	if (p[k] == k)
		return k;
	return p[k] = getParent(p[k]);
}
 
void setFriend(int a,int b)
{
	int pa = getParent(a);
	int pb = getParent(b);
	if (pa == pb)
		return;
	p[pa] = pb;
}
 
void dfs(int v,int p)
{
	used[v] = 1;
	tin[v] = ++timer;
	int l = 1;
	while ((1 << l) <= n)
		l++;
	up[v][0] = p;
	mn[v][0] = min(d[v],d[p]);
	for (int i = 1; i <= l; i++)
	{
		up[v][i] = up[up[v][i - 1]][i - 1];
		mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i-1]);
 
	}
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (used[to])
			continue;
		dfs(to,v);
	}
	tout[v] = ++timer;
}
 
bool upper(int a,int b)
{
	return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
 
int lcaAns(int a, int b)
{
	int l = 1;
	while ((1 << l) <= n)
		l++;
	int ans = min(d[a], d[b]);
	if (upper(a, b) && upper(b, a))
		return ans;
 
	int aa=a, bb=b;
	if (!upper(a, b))
	{
		for (int i = l; i >= 0; i--)
			if (!upper(up[a][i], b))
			{
				ans = min(ans, mn[a][i]);
				a = up[a][i];
				ans = min(d[a], ans);
			}
		ans = min(ans, mn[a][0]);
	}
	a = bb;
	b = aa;
 
	if (!upper(a, b))
	{
		for (int i = l; i >= 0; i--)
			if (!upper(up[a][i], b))
			{
				ans = min(ans, mn[a][i]);
				a = up[a][i];
				ans = min(d[a],ans);
			}
		ans = min(ans, mn[a][0]);
	}
	return ans;
}
 
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, D;
		street s;
		cin >> a >> b >> D;
		s.d = D;
		s.to = b;
		gr[a].PB(s);
		s.to = a;
		gr[b].PB(s);
		st.PB(MP(a, b));
	}
 
	for (int i = 0; i <= n; i++)
	{
		d[i] = mod;
		p[i] = i;
	}
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a;
		cin >> a;
		d[a] = 0;
		street s;
		s.to = a;
		s.d = d[a];
		q.push(s);
	}
 
 
	for (int j = 1; j <= n; j++)
	{
		street v;
		v.to = -1;
		v.d = -1;
		do
		{
			v = q.top();
			q.pop();
		} while (used[v.to]);
 
		if (v.to == -1)
			continue;
		used[v.to] = 1;
		for (int i = 0; i < (int)gr[v.to].size(); i++)
		{
			street to = gr[v.to][i];
			if (d[to.to] > v.d + to.d)
			{
				d[to.to] = v.d + to.d;
				street s;
				s.d = d[to.to];
				s.to = to.to;
				q.push(s);
			}
		}
	}
 
	sort(st.begin(), st.end(), [](pair<int, int> a, pair<int, int> b) {
		return min(d[a.first], d[a.second]) > min(d[b.first], d[b.second]);
	});
 
	for (int i = 0; i < st.size(); i++)
		if (getParent(st[i].first) != getParent(st[i].second))
		{
			setFriend(st[i].first,st[i].second);
			g[st[i].first].PB(st[i].second);
			g[st[i].second].PB(st[i].first);
		}
	memset(used, 0, 100005 * sizeof(int));
 
	p[1] = 0;
	tout[0] = mod;
	dfs(1,0);
 
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << lcaAns(a, b) << endl;
	}
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dfs(int, int)':
plan.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:191:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < st.size(); i++)
                  ~~^~~~~~~~~~~

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