Submission #341469

#	Time	Username	Problem	Language	Result	Execution time	Memory
341469		Tosic	Evacuation plan (IZhO18_plan)	C++14	54 / 100	1877 ms	53800 KiB

plan

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

int n, m, k, ans, iT[maxn], oT[maxn], gT;
vector<pair<int, pair<int, int>>> allEdgs;
vector<vector<pair<int, int>>> gr,tree;
multiset<pair<int, int> > cl;
int par[maxn], mxVal[maxn], anc[maxn][20], minV[maxn][20];

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

bool join(int x, int y){
	x = getP(x);
	y = getP(y);
	if(x != y){
		par[min(x,y)] = max(x,y);
		return true;
	}
	return 0;
}

void mst(){
	sort(allEdgs.begin(), allEdgs.end());
	reverse(allEdgs.begin(), allEdgs.end() );
	for(auto tmp : allEdgs){

		int u = tmp.second.first, v = tmp.second.second;
		if(join(u, v) ){
			tree[u].push_back({tmp.first, v});
			tree[v].push_back({tmp.first, u});
		}
	}
}

void dfs(int x, int p){
	iT[x] = gT;++gT;
	anc[x][0] = p;
	minV[x][0] = mxVal[x];
	minV[x][0] = min(minV[x][0], mxVal[p]);
	for(int i = 1; i < 20; ++i){
		anc[x][i] = anc[anc[x][i-1]][i-1];
		minV[x][i] = min(minV[x][i-1], minV[anc[x][i-1]][i-1]);
	}
	for(auto i : tree[x]){
		if(i.second != p){
			dfs(i.second, x);
		}
	}
	oT[x] = gT;
	++gT;
}

bool isX(int x, int y){
	return (iT[x] <= iT[y] and oT[x] >= oT[y]);
}

int getD(int x, int y){
	for(auto i : gr[x]){
		if(i.second == y){
			return min(mxVal[x], mxVal[y]);
		}
	}
	int lca = 0;
		int res = 1e9;
		for(int i = 19; i >= 0; --i){
			if(!isX(anc[x][i], y)){
				res = min(res, minV[x][i]);
				x = anc[x][i];
			}
		}
		if(isX(x, y)){
			lca = x;
		} else {
			lca = anc[x][0];
			res = min(res, minV[x][0]);
		}
		for(int i = 19; i >= 0; --i){
			if(!isX(anc[y][i], lca )){
				res = min(res, minV[y][i]);
				y = anc[y][i];
			}
		}
		if(y != lca){
			res=min(res,minV[y][0]);
		}
		return res;

}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m;
	gr.resize(n+1, vector<pair<int, int>>());
	tree = gr;
	for(int i = 0; i < m; ++i){
		int u,v,w;
		cin >> u >> v >> w;
		--u, v--;
		gr[u].push_back({w, v});
		gr[v].push_back({w, u});
	}
	cin >> k;
	for(int i = 0; i < k; ++i){
		int idx;
		cin>>idx;
		--idx;
		gr[n].push_back({0, idx});
		gr[idx].push_back({0, n});
	}
	cl.insert({0, n});
	mxVal[n] = 0;
	for(int i = 0; i < n; ++i){
		mxVal[i] = 1e9;
		par[i] = i;
	}
	while(!cl.empty()){
		int dst = cl.begin()->first, idx = cl.begin()->second;
		cl.erase(cl.begin());
		//cerr << dst << '\n';
		for(auto i : gr[idx]){
			if(mxVal[i.second] > dst + i.first){
				auto tmp = cl.find({mxVal[i.second], i.second});
				if(tmp != cl.end()){
					cl.erase(tmp);
				}
				mxVal[i.second] = dst+i.first;
				cl.insert({mxVal[i.second], i.second});
			}
		}
	}
	for(int i = 0; i < n; ++i){
		for(auto j : gr[i]){
			allEdgs.push_back( make_pair(min(mxVal[i],mxVal[j.second]), make_pair(i, j.second) ));
		}
	}
	//cerr << 'a';
	mst();
	//cerr << 'b';
	dfs(0, 0);
	for(int i = 0; i < n; ++i){
		cerr << mxVal[i] << ' ';
	}
	int q;
	cin>>q;
	for(int i = 0; i < q; ++i){
		int x, y;
		cin >> x >> y;
		--x,--y;
		cout << getD(x, y) << '\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: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46