Submission #174044

#	Time	Username	Problem	Language	Result	Execution time	Memory
174044		anakib1	Evacuation plan (IZhO18_plan)	C++17	54 / 100	4025 ms	106160 KiB

plan

/*

Sviatoslav Bidzilia 2019
CF: anakib1

*/

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)

template<typename A, typename B, typename C>
struct triple
{
	A X;
	B Y;
	C Z;
	triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0)
{
	return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b)
{
	if (a.X != b.X)
		return a.X < b.X;
	if (a.Y != b.Y)
		return a.Y < b.Y;
	return a.Z < b.Z;
}
template<typename A, typename B, typename C>
bool operator==(const triple<A, B, C>& a, const triple<A, B, C>& b)
{
	return a.X == b.X && a.Y == b.Y && a.Z == b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p)
{
	ofs << "( " << p.F << " , " << p.S << " )";
	return ofs;
}
template<typename T>
void print(T a)
{
	for (auto i : a)
		cout << i << ' ';
	cout << '\n';
}
template<typename T>
T max(T a, T b, T c)
{
	return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c)
{
	return min(a, min(b, c));
}
struct custom_hash
{
	static uint64_t splitmix64(uint64_t x)
	{
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
	size_t operator()(tii x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x.X + FIXED_RANDOM) ^ splitmix64(x.Y + FIXED_RANDOM) ^ splitmix64(x.Z + FIXED_RANDOM);
	}
};
#define mxn (int)(1e5)
int pos[mxn], now[mxn], ans[mxn];
vector<pii> g[mxn];
unordered_set<int> tre[mxn];
int d[mxn];
unordered_map<int, unordered_map<int, int> > direct;
unordered_set<tii, custom_hash> ask[mxn];
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	srand(time(NULL));

	int n, m;
	scanf("%d%d", &n, &m);
	rng(m)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		x--, y--;
		direct[x][y] = direct[y][x] = 1;
		g[x].pb(mp(y, z));
		g[y].pb(mp(x, z));
	}
	rngi(i, n)
		SORT(g[i]);
	rngi(i, n)
		d[i] = inf;
	set< pii > q;
	int k;
	scanf("%d", &k);
	rng(k)
	{
		int x;
		scanf("%d", &x);
		x--;
		d[x] = 0;
		q.insert(mp(0, x));
	}
	while (q.size())
	{
		int v = q.begin()->second;
		q.erase(q.begin());
		for (auto toe : g[v])
		{
			int to = toe.first;
			int l = toe.second;
			if (d[to] > d[v] + l)
			{
				q.erase(mp(d[to], to));
				d[to] = d[v] + l;
				q.insert(mp(d[to], to));
			}
		}
	}
	//print(d);
	vector<pii> b;
	rngi(i, n)
		b.pb(mp(d[i], i));
	sort(all(b), greater<pii>());

	rngi(i, n)
		pos[i] = now[i] = i;
	vi ss;
	int t;
	bool any = 1;
	scanf("%d", &t);
	rngi(i, t)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x--, y--;
		if (direct[x][y])
			ss.pb(min(d[x], d[y]));
		else
			any = 0;
		ask[x].insert(tii{ x, y, i });
		ask[y].insert(tii{ y,x,i });
	}
	if (any)
	{
		for (auto i : ss)
			cout << i << '\n';
		return 0;
	}
	rngi(i, b.size())
	{
		int v = b[i].second;
		int l = b[i].first;
		tre[v].insert(v);
		for (auto toe : g[v])
		{
			int to = toe.first;
			if (!tre[now[to]].size())
				continue;
			if (tre[now[v]].count(to))
				continue;

			vector<tii> del;
			for (tii qq : ask[pos[now[v]]])
				if (tre[now[to]].count(qq.Y))
				{
					del.pb(qq);
					ans[qq.Z] = l;
				}

			for (auto z : del)
				ask[pos[now[v]]].erase(z), ask[pos[now[to]]].erase(tii{ z.Y, z.X, z.Z });
			if (ask[pos[now[v]]].size() < ask[pos[now[to]]].size())
			{
				for (auto z : ask[pos[now[v]]])
					ask[pos[now[to]]].insert(z);
				pos[now[v]] = pos[now[to]];
			}
			else
			{
				for (auto z : ask[pos[now[to]]])
					ask[pos[now[v]]].insert(z);
				pos[now[to]] = pos[now[v]];
			}
			if (tre[now[v]].size() < tre[now[to]].size())
			{
				for (auto z : tre[now[v]])
					if (z != v)
					{
						tre[now[to]].insert(z);
						now[z] = now[to];
					}
				tre[now[to]].insert(v);
				now[v] = now[to];
			}
			else
			{

				for (auto z : tre[now[to]])
					if (z != to)
					{
						tre[now[v]].insert(z);
						now[z] = now[v];
					}
				tre[now[v]].insert(to);
				now[to] = now[v];
			}


		}

	}
	rngi(i, t)
		printf("%d\n", ans[i]);
}
/*
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
5
1 6
5 3
4 8
5 8
1 5

*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:47:13: warning: overflow in implicit constant conversion [-Woverflow]
 #define inf 1e17
             ^
plan.cpp:153:10: note: in expansion of macro 'inf'
   d[i] = inf;
          ^~~
plan.cpp:52:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rngi(i, x) for(int i = 0; i < (x); i++)
                                     ^
plan.cpp:211:2: note: in expansion of macro 'rngi'
  rngi(i, b.size())
  ^~~~
plan.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
plan.cpp:196:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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