Submission #174669

#	Time	Username	Problem	Language	Result	Execution time	Memory
174669		tselmegkh	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1853 ms	42136 KiB

plan

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

const int N = 1e5 + 5;

vector<pair<int, int>> g[N];
vector<int> newg[N];
int d[N], p[N], par[N], idx, h[N], e[2 * N], l[2 * N], tree[8 * N];
bool vis[N];

bool cmp(pair<int, int> a, pair<int, int> b){
	return (a.first > b.first);
}

int get(int u){
	if(u == p[u])return u;
	return p[u] = get(p[u]);
}
void unite(int u, int v){
	int pu = get(u), pv = get(v);
	if(pu != pv){
		p[pv] = pu;
		newg[u].push_back(v);
		newg[v].push_back(u);
	}
}
void dfs(int u, int depth){
	h[u] = idx;
	e[idx] = u;
	l[idx] = depth; idx++;
	for(int v : newg[u]){
		if(v == par[u])continue;
		dfs(v, depth + 1);
		e[idx] = u;
		l[idx] = depth; idx++;
	}
}

void build(int v, int L, int R){
	if(L == R){
		tree[v] = L;
		return;
	}
	int mid = (L + R) / 2;
	build(v * 2, L, mid);
	build(v * 2 + 1, mid + 1, R);
	if(l[tree[v * 2]] > l[tree[v * 2 + 1]])tree[v] = tree[v * 2 + 1];
	else tree[v] = tree[v * 2];
	return;
}
int query(int v, int L, int R, int ql, int qr){
	if(ql > R || qr < L)return -1;
	if(ql <= L && qr >= R)return tree[v];
	int mid = (L + R) / 2;
	int p1 = query(v * 2, L, mid, ql, qr), p2 = query(v * 2 + 1, mid + 1, R, ql, qr);
	if(p1 == -1)return p2;
	if(p2 == -1)return p1;
	if(l[p1] > l[p2])return p2;
	else return p1;
}
int main(){
	int n, m, k;
	cin >> n >> m;
	memset(d, 0x3f3f3f3f, sizeof d);
	for(int i = 1; i <= n; i++)p[i] = i;

	for(int i = 0; i < m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	cin >> k;

	set<pair<int, int>> s;
	for(int i = 0; i < k; i++){
		int loc;
		cin >> loc;
		d[loc] = 0;
		s.insert({0, loc});
	}
	while(!s.empty()){
		pair<int, int> x = *s.begin(); s.erase(s.begin());
		int u = x.second;
		for(auto vw : g[u]){
			int v = vw.first, w = vw.second;
			if(d[v] > d[u] + w){
				d[v] = d[u] + w;
				s.insert({d[v], v});
			}
		}
	}
	vector<pair<int, int>> v;
	for(int i = 1; i <= n; i++){
		v.push_back({d[i], i});
	}
	sort(v.begin(), v.end(), cmp);

	int root = -1;
	for(auto x : v){
		int u = x.second;
		vis[u] = 1;
		root = u;
		for(auto y : g[u]){
			int to = y.first;
			if(vis[to]){
				to = get(to);
				if(u != to){
					unite(u, to);
					par[to] = u;
				}
			}		
		}
	}
	dfs(root, 0);
	build(1, 0, idx - 1);

	int q;
	cin >> q;
	while(q--){
		int u, v;
		cin >> u >> v;
		int ql = h[u], qr = h[v];
		if(ql > qr)swap(ql, qr);
		cout << d[e[query(1, 0, idx - 1, ql, qr)]] << '\n';
	}
}

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