Submission #92272

#	Time	Username	Problem	Language	Result	Execution time	Memory
92272		Nodir_Bobiev	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4086 ms	26696 KiB

plan

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

using namespace std;

const long long N = 1e5 + 100;

int n, k, m, Q;
int dist[N];
int S[N], T[N], p[N];
int ans[N];
int used[N];
vector < pair < int, int > > gr[N];
queue < int > q;
set < pair < int, int > > st;  
set < int > IDS[N];


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

void union_sets(int x, int y, int ds)
{
	x = FIND(x);
	y = FIND(y);
	if(x == y)return;
	for (auto id: IDS[x]){
		if(ans[id] == -1 && IDS[y].find(id) != IDS[y].end()){
			ans[id] = ds;
			IDS[y].erase(id);
		}
	}
	for(auto id: IDS[y])
		IDS[x].insert(id);
	
	IDS[y].clear();
	p[y] = x;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	while(m--){
		int a, b, w;
		cin >> a >> b >> w;
		gr[a].push_back({w, b});
		gr[b].push_back({w, a});
	}
	fill(dist, dist + N, 1e9);
	fill(ans, ans + N, -1);
	iota(p, p + N, 0);
	cin >> k;
	
	while(k--){
		int a; cin >> a;
		dist[a] = 0;
		q.push(a);
	}
	// algorithm dejikstra
	
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(auto to: gr[v]){
			if(dist[to.second] > dist[v] + to.first){
				dist[to.second] = dist[v] + to.first;
				q.push(to.second);
			}
		}
	}
	//////////////////////////////
	
	for (int i = 1; i <= n; i++)
		st.insert({-dist[i], i});
	
	cin >> Q;
	for (int i = 1; i <= Q; i++){
		cin >> S[i] >> T[i];
		IDS[S[i]].insert(i);
		IDS[T[i]].insert(i);
	}
	
	for (auto it = st.begin(); it != st.end(); it++){
		int v = it -> second;
		used[v] = true;
		for(auto to: gr[v]){
			if(used[to.second] == false)continue;
			union_sets(v, to.second, dist[v]);
		}
	}
	for (int i = 1; i <= Q; i++)
		cout << ans[i] << 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: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46