Submission #341607

#	Time	Username	Problem	Language	Result	Execution time	Memory
341607		Tosic	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1466 ms	59336 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<pair<int, int>> allVr;
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 maxS(){
	sort(allVr.begin(), allVr.end());
	reverse(allVr.begin(), allVr.end() );
	for(int i = 0; i < allVr.size(); ++i){
		auto tmp = allVr[i];
		int u = tmp.second;
		for(auto tmpV:gr[u]){
            int v = tmpV.second;
			if(mxVal[v] >= mxVal[u] and 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 Lca(int x, int y){
	if(isX(x, y)){
		return x;
	} else if(isX(y, x)){
		return y;
	} else {
		for(int i = 19; i >= 0; --i){
			if(!isX(anc[x][i], y)){
				x = anc[x][i];
			}
		}
		return anc[x][0];
	}
	return 0;
}

int getV(int lca, int x){
	// lca is above x
	int res = minV[x][0];
	for(int i = 19; i >= 0; --i){
		if(!isX(anc[x][i], lca)){
			res = min(res, minV[x][i]);
			x = anc[x][i];
			res = min(res, minV[x][0]);
		}
	}
	res=min(res,minV[lca][0]);
	return res;
}

int getD(int x, int y){
	for(auto i : gr[x]){
		if(i.second == y){
			return min(mxVal[x], mxVal[y]);
		}
	}
	int lca = Lca(x, y);
	int res = min(getV(lca, x), getV(lca, y));
	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 < n; ++i){
		mxVal[i] = 1e9;
		par[i] = i;
	}
	for(int i = 0; i < k; ++i){
		int idx;
		cin>>idx;
		--idx;
		cl.insert({0, idx});
		mxVal[idx] = 0;
	}
	
	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) ));
		}
		allVr.push_back({mxVal[i], i});
	}
	//cerr << 'a';
	maxS();
	//cerr << 'b';
	dfs(0, 0);
	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*/
}

Compilation message (stderr)

plan.cpp: In function 'void maxS()':
plan.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i = 0; i < allVr.size(); ++i){
      |                 ~~^~~~~~~~~~~~~~

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