Submission #492359

#	Time	Username	Problem	Language	Result	Execution time	Memory
492359		vuhoanggiap	Evacuation plan (IZhO18_plan)	C++17	100 / 100	798 ms	23556 KiB

plan

#include <bits/stdc++.h>
#define ii pair<int, int> 
#define fi first
#define se second 
#define pb push_back 
using namespace std;

const int maxN = 1e5 + 1, INF = 1e9; // m = 5e5; overflow?
int n, m, k, q; 

vector<ii> adj[maxN];
int npp[maxN];  
int dist[maxN];
int idSorted[maxN];  

void dijk() {
	for (int i = 1; i <= n; i++) 
		dist[i] = INF;
	for (int i = 1; i <= k; i++) 
		dist[npp[i]] = 0; 
	priority_queue<ii, vector<ii>, greater<ii> > pq; 
	for (int i = 1; i <= k; i++) 
		pq.push({0, npp[i]}); 
	while (!pq.empty()) {
		int d, u;
		tie(d, u) = pq.top(); pq.pop();  
		if (d != dist[u])
			continue; 
		for (auto T : adj[u]) {
			int v, w; tie(v, w) = T; 
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w; 
				pq.push({dist[v], v}); 
			}
		}
 	}
}

struct node {
	int l, r; 
	vector<int> query; 
};

int s[maxN], t[maxN]; 
int ans[maxN]; // 1->q
 
int p[maxN], sz[maxN]; 
int find(int u) {
	return u == p[u] ? u : p[u] = find(p[u]); 
}
void merge(int u, int v) {
	u = find(u), v = find(v); 
	if (u == v) 
		return; 
	if (sz[u] < sz[v]) 
		swap(u, v); 
	p[v] = u; 
	sz[u] += sz[v]; sz[v] = 0; 
}

void init() {
	for (int i = 1; i <= n; i++) 
		p[i] = i, sz[i] = 1; 
}

bool vis[maxN];

void reset(int &cur) {
	cur = n + 1;  
	for (int i = 1; i <= n; i++) 
		vis[i] = false; 
	init(); 
}

void solve() {
	cin >> q; 
	queue<node> Q;  
	node tmp; tmp.l = 1, tmp.r = n; 
	for (int i = 1; i <= q; i++) {
		cin >> s[i] >> t[i]; 
		tmp.query.pb(i); 
	}
	Q.push(tmp); 
	int cur = n + 1; 
	reset(cur); 
	while (!Q.empty()) {
		tmp = Q.front(); Q.pop(); 
		int l = tmp.l, r = tmp.r; 
		if (l == r) {
			for (auto id : tmp.query)
				ans[id] = dist[idSorted[l]]; 
			continue; 
		}
		int mid = (l + r) >> 1;
		if (cur < r) {
			reset(cur); 
		}
		while (cur > mid + 1) {
			int u = idSorted[cur - 1]; 
			vis[u] = true; 
			for (auto T : adj[u]) {
				int v = T.fi;  
				if (vis[v]) 
					merge(u, v); 
			}
			cur--; 
		}
		node lef, rig;
		lef.l = l; lef.r = mid; 
		rig.l = mid + 1; rig.r = r; 
		for (auto id : tmp.query) {
			if (find(s[id]) == find(t[id]))
				rig.query.pb(id); 
			else 
				lef.query.pb(id); 
		} 
		Q.push(rig); 
		Q.push(lef); 
	}
	for (int i = 1; i <= q; i++) 
		cout << ans[i] << '\n'; 
}

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cin >> n >> m; 
	for (int i = 1; i <= m; i++) {
		int u, v, w; cin >> u >> v >> w; 
		adj[u].pb({v, w}); 
		adj[v].pb({u, w}); 
	}
	cin >> k; 
	for (int i = 1; i <= k; i++) {
		cin >> npp[i]; 
	}
	dijk(); 
//	cout << "dist: \n"; 
//	for (int i = 1; i <= n; i++) 
//		cout << dist[i] << ' '; cout << '\n'; 
	for (int i = 1; i <= n; i++)
		idSorted[i] = i; 
	sort(idSorted + 1, idSorted + n + 1, [&](const int &x, const int &y) {
		return dist[x] < dist[y]; 
	}); 
//	cout << "idsorted: "; for (int i = 1; i <= n; i++) cout << idSorted[i] << ' '; cout << '\n'; 
	init(); 
	solve(); 
}

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