Submission #498099

#	Time	Username	Problem	Language	Result	Execution time	Memory
498099		Ierus	Evacuation plan (IZhO18_plan)	C++17	22 / 100	3342 ms	35396 KiB

plan

#include<bits/stdc++.h>

using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
const int N = 1e5+777;
int n, m;
vector<pair<int,int>> g[N];
struct Dsu{
	int n;
	vector<int> p, sm;
	Dsu(int _n){
		n = _n;
		p.resize(n+2);
		sm.resize(n+2);
		for(int i = 1; i <= n; ++i){
			p[i] = i;
			sm[i] = i;
		}
	}
	int get(int v){
		if(p[v] == v) return v;
		return p[v] = get(p[v]);
	}
	bool merge(int x, int y){
		x = get(x), y = get(y);
		if(x == y){
			return false;
		}
		if(sm[x] < sm[y]){
			swap(x, y);
		}
		sm[x] += sm[y];
		p[y] = x;
		return true;
	}
}dsu(N);
struct node{
	int w, v, u;
}edge[N];
vector<int> d(N, INT_MAX);
inline void dijikstra(){
	set<pair<int,int>> st;
	int t; cin >> t;
	for(int i = 1; i <= t; ++i){
		int v; cin >> v;
		st.insert({d[v]=0, v});
	}
	while(!st.empty()){
		int v = st.begin() -> S;
		st.erase(st.begin());
		for(auto to : g[v]){
			if(d[to.F] > d[v] + to.S){
				st.erase({d[to.F], to.F});
				st.insert({d[to.F]=d[v]+to.S,to.F});
			}
		}
	}
	cerr << "D\n";
	for(int i = 1; i <= n; ++i){
		cerr << "d[" << i << "]: " << d[i] << '\n';
	}
}
const int LG = 18;
int tin[N], tout[N], timer, up[N][LG+2], mn[N][LG+2], lev[N];
void dfs(int v, int p, int w = 0){
	lev[v] = lev[p] + 1;
	up[v][0] = p;
	mn[v][0] = w;
	for(int L = 1; L <= LG; ++L){
		up[v][L] = up[up[v][L-1]][L-1];
		mn[v][L] = min(mn[v][L-1], mn[up[v][L-1]][L-1]);
	}
	tin[v] = ++timer;
	for(auto to : g[v]){
		if(to.F != p){
			dfs(to.F, v, to.S);
		}
	}
	tout[v] = timer;
}
bool upper (int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca (int a, int b) {
	if (upper(a, b))  return a;
	if (upper(b, a))  return b;
	for (int i = LG; i >= 0; --i)
		if (!upper (up[a][i], b))
			a = up[a][i];
	return up[a][0];
}
int get(int x, int y){
	int ans = d[x];
	for(int k = LG; k >= 0; k--){
		if(lev[x] - (1<<k) >= lev[y]){
	    	ans = min(ans, mn[x][k]);
	    	x = up[x][k];
		}
	}
  return ans;
}
set<int> e;
void precalc(){
	dijikstra();
	for(int i = 1; i <= n; ++i){
		g[i].clear();
	}
	priority_queue<tuple<int,int,int>> pq;
	cerr << "changed\n";
	for(int i = 1; i <= m; ++i){
		edge[i].w = min(d[edge[i].v], d[edge[i].u]);
		cerr << edge[i].v << ' ' << edge[i].u << ' ' << edge[i].w << '\n';
		pq.push(make_tuple(edge[i].w, edge[i].v, edge[i].u));
	}
	while(!pq.empty()){
		int x, y, w;
		tie(w, x, y) = pq.top();
		pq.pop();
		if(dsu.merge(x, y)){
			e.insert(x), e.insert(y);
			cerr << "x: " << x << " y: " << y << " w: " << w << '\n';
			g[x].pb({y, w});
			g[y].pb({x, w});
		}
	}
	dfs(1, 1);
}
int main(){NFS;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		cin >> edge[i].v >> edge[i].u >> edge[i].w;
		g[edge[i].v].pb({edge[i].u,edge[i].w});
		g[edge[i].u].pb({edge[i].v,edge[i].w});
	}
	precalc();
	for(auto it : e){
		cerr << it << " tin["<<it<<"]: " << tin[it] << " tout["<<it<<"]: " << tout[it] << '\n'; 
	}
	int que; cin >> que;
	for(int x, y; que--;){
		cin >> x >> y;
		int p = lca(x, y);
		int res1 = get(x, p);
		int res2 = get(y, p);
		cerr << "p: " << p << '\n';
		cout << min(res1, res2) << '\n';
	}
};
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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