Submission #743563

#	Time	Username	Problem	Language	Result	Execution time	Memory
743563		LeonaRaging	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1095 ms	33552 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define T pair<int,int>
#define pb emplace_back
#define db(val) "[" #val " = " << (val) << "] "

const int maxn = 1e5 + 4;

struct DisjointSet {
	vector<int> par, Rank;
	DisjointSet(int n) {
		par.resize(n + 4); Rank.resize(n + 4);
		for (int i = 1; i <= n; i++)
			par[i] = i, Rank[i] = 1;
	}
	int find(int x) {
		if (x != par[x]) par[x] = find(par[x]);
		return par[x];
	}
	bool join(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return 0;
		if (Rank[u] < Rank[v]) swap(u, v);
		Rank[u] += Rank[v];
		par[v] = u;
		return 1;
	}
};

int n, m, dis[maxn], s[maxn], t[maxn], L[maxn], R[maxn], res[maxn];
vector<T> adj[maxn];
T node[maxn];
vector<int> vals, myVec[maxn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++) {
    	cin >> u >> v >> w;
    	adj[u].pb(v, w);
    	adj[v].pb(u, w);
    }
    priority_queue<T, vector<T>, greater<T>> pq;
    int q; cin >> q;
    memset(dis, 63, sizeof dis);
    while (q--) {
    	int u; cin >> u;
    	pq.push({0, u});
    	dis[u] = 0;
    }
    while (!pq.empty()) {
    	int d, u; tie(d, u) = pq.top(); pq.pop();
    	node[u] = {dis[u], u};
    	if (dis[u] != d) continue;
    	for (auto it : adj[u]) {
    		int v, w; tie(v, w) = it;
    		if (dis[u] + w < dis[v])
    			dis[v] = dis[u] + w,
    			pq.push({dis[v], v});
    	}
    }
    sort(node + 1, node + 1 + n);
    sort(vals.begin(), vals.end());
    cin >> q;
    for (int i = 1; i <= q; i++)
    	cin >> s[i] >> t[i],
    	L[i] = 1, R[i] = n;
    for (int time = 1; time <= 17; time++) {
    	for (int i = 1; i <= q; i++)
    		myVec[(L[i] + R[i]) / 2].pb(i);
    	DisjointSet Dsu(n);
    	for (int i = n; i >= 1; i--) {
    		int u = node[i].second;
    		for (auto it : adj[u]) {
    			int v, w; tie(v, w) = it;
    			if (dis[v] >= dis[u])
    				Dsu.join(u, v);
    		}
    		while (!myVec[i].empty()) {
    			int id = myVec[i].back(); myVec[i].pop_back();
    			if (Dsu.find(s[id]) == Dsu.find(t[id]))
    				res[id] = dis[u],
    				L[id] = i + 1;
    			else R[id] = i - 1;
    		}
    	}
    }
    for (int i = 1; i <= q; i++)
    	cout << res[i] << '\n';
}

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