Submission #91242

#	Time	Username	Problem	Language	Result	Execution time	Memory
91242		Nodir_Bobiev	Evacuation plan (IZhO18_plan)	C++14	100 / 100	3091 ms	31488 KiB

plan

# include <iostream>
# include <vector>
# include <queue>
# include <algorithm>
# include <set>

# define ll long long
# define fi first
# define se second

using namespace std;

const int N = 1e5 + 10;

int n, m, Q, k;
int dist[N];
int l[N], r[N], p[N];
int s[N], t[N];
bool good[N];
vector < pair < int, int > > gr[N];
vector < pair < int, int > > st;
vector < int > mdl[N];
set < pair < int, int > > ss;


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

void unionSets(int x, int y)
{
	x = fnd(x);
	y = fnd(y);
	p[x] = y;
}

int main()
{ 
	fill(dist, dist + N, 1000000000);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int a, b, w; 
		cin >> a >> b >> w;
		gr[a].push_back({b, w});
		gr[b].push_back({a, w});
	}
	
	cin >> k;
	while(k--){
		int a;	cin >> a;
		dist[a] = 0;
		ss.insert({0, a});
	}
	while(!ss.empty()){
		pair < int, int > v = *ss.begin();
		ss.erase(ss.begin());
		for (auto to : gr[v.se]){
			if(dist[to.fi] > dist[v.se] + to.se){
				ss.erase({dist[v.se], v.se});
				dist[to.fi] = dist[v.se] + to.se;
				ss.insert({dist[to.fi], to.fi});
			}
		}
	}
	cin >> Q;
	for (int i = 1; i <= Q; i++){
		cin >> s[i] >> t[i];
		l[i] = -1;
		r[i] = n - 1;
	}	
	
	for (int i = 1; i <= n; i++)
		st.push_back({dist[i], i});
	
	
	sort(st.begin(), st.end());
	reverse(st.begin(), st.end());
	
	while(true){
		bool T = false;
		
		for (int i = 0; i <= n; i++){
			mdl[i].clear();
			p[i] = i,	good[i] = false;
		}
		for (int i = 1; i <= Q; i++){
			if(l[i] < r[i] - 1){
				T = true;
				mdl[(l[i] + r[i]) / 2].push_back(i);
			}
		}
		if(!T)break;
		
		for (int i = 0; i < n; i++){
			good[st[i].se] = true;
			
			for (auto to : gr[st[i].se])
				if(good[to.fi])
					unionSets(to.fi, st[i].se);
			
			for (auto c: mdl[i]){
				if(fnd(s[c]) != fnd(t[c]))
					l[c] = i;
				else 
					r[c] = i;
			}
		}
	}
	for (int i = 1; i <= Q; i++){
		cout << st[r[i]].fi <<endl;
	}	
	
}
/*
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: 46 / 46