Submission #1098211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098211		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	894 ms	53328 KiB

plan

//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//#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 file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
//#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;

const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};

int rnd() {
	int x = rand() << 15;
	return x ^ rand();
}

int a[N], p[N], d[N], qv[N], qu[N], L[N], R[N];
vector <pair<int, int>> g[N];

int get(int v) {
	if (v == p[v]) return v;
	return p[v] = get(p[v]);
}

void dsu(int v, int u, int tm) {
	if (min(d[v], d[u]) < tm) return;
	v = get(v);
	u = get(u);
	if (v == u) return;
	if (rand() % 2) {
		p[v] = u;
	} else {
		p[u] = v;
	}
}

void GazizMadi() {
	int n, m;
	cin >> n >> m;
	while (m--) {
		int v, u, w;
		cin >> v >> u >> w;
		g[v].pb({u, w});
		g[u].pb({v, w});
	}

	for (int i = 1; i <= n; i++) {
		d[i] = MOD;
	}
	cin >> m;
	set <pair<int, int>> s;
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
		d[a[i]] = 0;
		s.insert({0, a[i]});
	}
	while (len(s)) {
		pair<int, int> now = *s.begin();
		s.erase(s.begin());
		int v = now.S;
//		cerr << "DJIS " << v << ' ' << d[v] << '\n';
		for (auto [u, w]: g[v]) if (d[v] + w < d[u]) {
			s.erase({d[u], u});
			d[u] = d[v] + w;
			s.insert({d[u], u});
		}
	}
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> qv[i] >> qu[i];
		L[i] = 1;
		R[i] = 1e9;
	}
	vector <pair<int, int>> ord;
	for (int i = 1; i <= n; i++) {
		ord.pb({d[i], i});
//		cerr << i << ' ' << d[i] << '\n'; 
	}
	sort(all(ord), greater<pair<int, int>>());
	while (true) {
		vector <pair<int, int>> cur;
		for (int i = 1; i <= q; i++) {
			if (L[i] <= R[i]) {
				cur.pb({((L[i] + R[i]) >> 1), i});			
			}
		}
		if (!len(cur)) break;
		sort(all(cur), greater<pair<int, int>>());
		int j = 0;
		for (int i = 1; i <= n; i++) p[i] = i;
		for (auto [x, i]: cur) {
			while (j < n && ord[j].F >= x) {
				int v = ord[j].S;
				for (auto [u, w]: g[v]) dsu(v, u, x);
				j++;
			}
			if (get(qv[i]) == get(qu[i])) L[i] = x + 1;
			else R[i] = x - 1;
		}
	}
	for (int i = 1; i <= q; i++) cout << R[i] << '\n';
	
}

const bool Cases = 0;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	srand(time(0));
	int TT = 1;
	if (Cases) cin >> TT;
	for (int i = 1; i <= TT; i++) {
		//cout << "Case " << i << ": ";
		GazizMadi();
	}
}

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