제출 #1107836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1107836		Muhammet	Evacuation plan (IZhO18_plan)	C++17	100 / 100	494 ms	119804 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()

vector <int> p, z, p1, h;

vector <vector <pair<int,int>>> v;

vector <vector <int>> sp, v2;

vector <int> a;

int par(int x){
	if(p[x] == x) return x;
	return p[x] = par(p[x]);
}

int lca(int x, int y){
	if(h[x] < h[y]) swap(x,y);
	for(int i = 20; i >= 0; i--){
		if(h[x] - (1<<i) >= h[y]){
			x = (sp[x][i]);
		}
	}
	for(int i = 20; i >= 0; i--){
		if(sp[x][i] != sp[y][i]){
			x = sp[x][i];
			y = sp[y][i];
		}
	}
	if(x == y) return z[x];
	return z[p1[x]];
}

void dfs(int x, int y){
	h[x] = h[y]+1;
	for(auto i : v2[x]){
		if(i != y){
			dfs(i,x);
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	v.resize(n+1);
	for(int i = 1; i <= m; i++){
		int u1, u2, w;
		cin >> u1 >> u2 >> w;
		v[u1].push_back({u2,w});
		v[u2].push_back({u1,w});
	}
	int k;
	cin >> k;
	a.resize(k+1);
	for(int i = 1; i <= k; i++){
		cin >> a[i];
	}
	priority_queue <pair<int,int>> q;
	vector <int> dis(n+1,1e9);
	for(int i = 1; i <= k; i++){
		q.push({0,a[i]});
		dis[a[i]] = 0;
	}
	while(!q.empty()){
		auto [w1,i] = q.top();
		q.pop();
		w1 *= (-1);
		if(dis[i] != w1) continue;
		for(auto [j,w] : v[i]){
			if(dis[j] > dis[i] + w){
				dis[j] = dis[i] + w;
				q.push({-dis[j],j});
			}
		}
	}
	vector <pair<int,int>> v1;
	vector <int> vis(n+1,0);
	p.resize(3*n+1);
	z.resize(3*n+1);
	p1.resize(3*n+1,0);
	for(int i = 1; i <= n; i++){
		p[i] = i;
		v1.push_back({dis[i],i});
	}
	sort(v1.rbegin(), v1.rend());
	v2.resize(3*n);
	int cnt = n;
	for(auto [w,i] : v1){
		cnt++;
		vis[i] = true;
		p[cnt] = cnt;
		p[i] = cnt;
		p1[i] = cnt;
		for(auto [j,w1] : v[i]){
			if(vis[j] == true){
				int i1 = par(i), j1 = par(j);
				if(i1 == j1) continue;
				p[j1] = i1;
				p1[j1] = i1;
				v2[cnt].push_back(j1);
				// cout << cnt << " " << j << ' ' << j1 << ' ' << i1 << '\n';
			}
		}
		v2[cnt].push_back(i);
		// cout << "a " << i << ' ' << cnt << "\n";
		z[cnt] = w;
	}
	sp.resize(2*cnt, vector <int> (35));
	h.resize(2*cnt, 0);
	for(int i = 1; i <= cnt; i++){
		sp[i][0] = p1[i];
	}
	for(int j = 1; j <= 20; j++){
		for(int i = 1; i <= cnt; i++){
			sp[i][j] = sp[sp[i][j-1]][j-1];
		}
	}
	dfs(cnt,0);
	int Q;
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		int s, t;
		cin >> s >> t;
		cout << lca(s,t) << "\n";
	}
}

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