Submission #1098187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098187		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	750 ms	524288 KiB

plan

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll int
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 1e5 + 7;

using namespace std;
using namespace __gnu_pbds;

ll n, m, k, p[N], a, b, c, ans, d[N], l, r, used[N], res, h[N], up[N][22], sz[N], dep[N], bc[N], tin[N], timer, t[N * 4];
set <pair <ll, ll>> s;
vector <pair <ll, ll>> g[N];

void upd (ll idx, ll val, ll tl = 1, ll tr = n, ll v = 1){
	if (tr < idx || tl > idx){
		return;
	}
	if (tl == tr && tl == idx){
		t[v] = val;
		return;
	}
	ll tm = (tl + tr) / 2;
	upd (idx, val, tl, tm, v + v);
	upd (idx, val, tm + 1, tr, v + v + 1);
	t[v] = min (t[v + v], t[v + v + 1]);
}

ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (tr < l || tl > r){
		return 1e9;
	}
	if (l <= tl && tr <= r){
		return t[v];
	}
	ll tm = (tl + tr) / 2;
	return min (get (l, r, tl, tm, v + v), get (l, r, tm + 1, tr, v + v + 1));
}

void dfs (ll v, ll md){
	if (d[v] < md){
		return;
	}
	if (c){
		return;
	}
	if (v == b){
		c = 1;
		return;
	}
	used[v] = 1;
	for (int i = 0; i < g[v].size(); i++){
		if (used[g[v][i].F] == 0 && d[g[v][i].F] >= md){
			dfs (g[v][i].F, md);
		}
	}
}

void clc (ll v, ll pp){
	sz[v] = 1;
	up[v][0] = pp;
	for (int i = 1; i <= 21; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i].F == pp){
			continue;
		}
		dep[g[v][i].F] = dep[v] + 1;
		clc (g[v][i].F, v);
		sz[v] += sz[g[v][i].F];
		if (sz[bc[v]] < sz[g[v][i].F]){
			bc[v] = g[v][i].F;
		}
	}
}

void mke (ll v, ll pp, ll hd){
	tin[v] = ++timer;
	upd (tin[v], d[v]);
	h[v] = hd;
	if (bc[v] > 0){
		mke (bc[v], v, hd);
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i].F != pp && g[v][i].F != pp){
			mke (g[v][i].F, v, g[v][i].F);
		}
	}
}

ll lca (ll a, ll b){
	if (dep[a] < dep[b]){
		swap (a, b);
	}
	ll c = abs (dep[a] - dep[b]);
	for (int i = 21; i >= 0; i--){
		if ((c >> i) & 1){
			a = up[a][i];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = 21; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb ({a, c});
	}
	dep[1] = 1;
	for (int i = 1; i <= n; i++){
		d[i] = 1e9;
	}
	cin >> k;
	for (int i = 1; i <= k; i++){
		cin >> p[i];
		d[p[i]] = 0;
	}
	for (int i = 1; i <= n; i++){
		s.insert({d[i], i});
	}
	while (s.size()){
		pair <ll, ll> opa = *s.begin();
		s.erase (opa);
		ll v = opa.second, w = opa.F;
		for (int i = 0; i < g[v].size(); i++){
			if (d[g[v][i].F] > w + g[v][i].S){
				s.erase ({d[g[v][i].F], g[v][i].F});
				d[g[v][i].F] = w + g[v][i].S;
				s.insert ({d[g[v][i].F], g[v][i].F});
			}
		}
	}
	clc (1, 0);
	mke (1, 0, 1);
	cin >> k;
//	if (n * k <= 1e6){
//		while (k--){
//			cin >> a >> b;
//			l = 0, r = 1e8, res = 0;
//			while (l <= r){
//				ll md = (l + r) / 2;
//				c = 0;
//				for (int i = 1; i <= n; i++){
//					used[i] = 0;
//				}
//				dfs (a, md);
//				if (c){
//					l = md + 1;
//					res = md;
//				}
//				else{
//					r = md - 1;
//				}
//			}
//			cout << res << '\n';
//		}
//		return 0;
//	}
//	else{
		cin >> a >> b;
		ll lc = lca (a, b);
		ans = 1e9;
		while (true){
			ans = min (ans, d[a]);
			if (a == lc){
				break;
			}
			if (a == h[a]){
				a = up[a][0];
				ans = min (ans, d[a]);
			}
			else{
				if (dep[lc] >= dep[h[a]]){
					ans = min (ans, get (tin[lc], tin[a]));
					break;
				}
				else{
					ans = min (ans, get (tin[h[a]], tin[a]));
					a = h[a];
					a = up[a][0];
					ans = min (ans, d[a]);
				}
			}
		}
		while (true){
			ans = min (ans, d[b]);
			if (b == lc){
				break;
			}
			if (b == h[b]){
				b = up[b][0];
				ans = min (ans, d[b]);
			}
			else{
				if (dep[lc] >= dep[h[b]]){
					ans = min (ans, get (tin[lc], tin[b]));
					break;
				}
				else{
					ans = min (ans, get (tin[h[b]], tin[b]));
					b = h[b];
					b = up[b][0];
					ans = min (ans, d[b]);
				}
			}
		}
		cout << ans << '\n';
//	}
}
/*
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 'void dfs(int, int)':
plan.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~
plan.cpp: In function 'void clc(int, int)':
plan.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~
plan.cpp: In function 'void mke(int, int, int)':
plan.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:154:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for (int i = 0; i < g[v].size(); i++){
      |                   ~~^~~~~~~~~~~~~

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