Submission #92370

#	Time	Username	Problem	Language	Result	Execution time	Memory
92370		Nodir_Bobiev	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1016 ms	62468 KiB

plan

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

using namespace std;

const int N = 1e5 + 100;

int n, k, m, Q;
int dist[N], S[N], T[N], p[N], ans[N];
bool 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;
	
	if((int)IDS[x].size() > (int)IDS[y].size())swap(x, y);
	
	for (auto id: IDS[x]){
		if(ans[id] == -1 && IDS[y].find(id) != IDS[y].end())
			ans[id] = ds;
	}
	
	for(auto id: IDS[x])
		IDS[y].insert(id);
	
	p[x] = y;
}


int main()
{
	scanf("%d %d", &n, &m);
	while(m--){
		int a, b, w;
		scanf("%d %d %d", &a,&b, &w);
		gr[a].push_back({w, b});
		gr[b].push_back({w, a});
	}
	fill(dist, dist + N, 1e8);
	fill(ans, ans + N, -1);
	iota(p, p + N, 0);
	
	scanf("%d", &k);	
	while(k--){
		int a; scanf("%d", &a);
		dist[a] = 0;
		q.push(a);
	}
	
	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});
	
	scanf("%d", &Q);
	for (int i = 1; i <= Q; i++){
		scanf("%d %d", 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])
				union_sets(to.second, v, dist[v]);
		}
	}
	for (int i = 1; i <= Q; i++)
		printf("%d\n", ans[i]);

}

/*
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 'int main()':
plan.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a,&b, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k); 
  ~~~~~^~~~~~~~~~
plan.cpp:61:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
plan.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
plan.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", S + i, T + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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