Submission #634609

#	Time	Username	Problem	Language	Result	Execution time	Memory
634609		drkarlicio2107	Evacuation plan (IZhO18_plan)	C++14	19 / 100	907 ms	42204 KiB

plan

#include <bits/stdc++.h>
using namespace std;
vector < pair <int, long long int> > g [100010];
 long long int dist [100010]; set < pair <long long int, long long int> > s;
 long long int P [100010];  long long int d [100010];  long long int bio [100010];
vector <pair <int, int> > qr [100010];
 long long int ans [100010];  long long int vis [100010];
vector < pair <long long int, long long int> > kr;
 long long int p ( long long int x) { return (P[x]!=x ? P [x]=p (P[x]) : P[x]); } ;
  long long int W;
void spoji ( long long int x,  long long int y){
	x=p (x); y=p (y);
	if (x==y) return ;
	if (qr [x].size()<qr [y].size()) swap (x, y);
	P [y]=x;
	for ( long long int i=0; i<qr [y].size(); i++){
		if (p (y)==p(qr[y][i].first)) ans [qr[y][i].second]=max (ans [qr[y][i].second], W);
		else qr [x].push_back ({qr[y][i].first, qr[y][i].second});
	}
	return ;
}
 int main(){
	 long long int n, m; cin >> n >> m;
	for ( long long int i=1; i<n+1; i++){
		dist [i]=(int)1e18; P [i]=i; d[i]=1;
	}
	for ( long long int i=1; i<n+1; i++) s.insert ({dist [i], i});
	for ( long long int i=0; i<m; i++){
		 long long int a, b, c; cin >> a >> b >> c;
		g [a].push_back ({b, c});
		g [b].push_back ({a, c});
	}
	 long long int k; cin >> k; 
	for ( long long int i=0; i<k; i++){
		 long long int a; cin >> a;
		s.erase ({dist [a], a});
		dist [a]=0;
		s.insert ({dist [a], a});
	}
	for ( long long int j=0; j<n-k; j++){
		 long long int x=(*s.begin()).second;
		s.erase ({dist [x], x});
		for ( long long int i=0; i<g [x].size(); i++){
			 long long int y=g [x][i].first;
			if (dist [y]>dist [x]+g [x][i].second){
				s.erase ({dist [y], y});
				dist [y]=dist [x]+g [x][i].second; 
				s.insert ({dist [y], y});
			}
		}
	}
	 long long int q; cin >> q;
	for ( long long int i=0; i<q; i++){
		 long long int x, y; cin >> x >> y;
		qr [x].push_back ({y, i});
		qr [y].push_back ({x, i});
	}
	for ( long long int i=1; i<n+1; i++)  {
		kr.push_back ({dist [i], i});
	}
	sort (kr.begin(), kr.end(), greater < pair <long long int, long long int> > ());
	for ( long long int i=0; i<kr.size(); i++){
		 long long int x=kr [i].second; W=kr [i].first; vis [x]=1;
		for ( long long int j=0; j<g [x].size(); j++){
			 long long int y=g [x][j].first;
			if (vis [y]){
				spoji (x, y);
			}
		}
	}
	for ( long long int i=0; i<q; i++) cout << ans [i] << endl;
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void spoji(long long int, long long int)':
plan.cpp:16:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for ( long long int i=0; i<qr [y].size(); i++){
      |                           ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:43:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for ( long long int i=0; i<g [x].size(); i++){
      |                            ~^~~~~~~~~~~~~
plan.cpp:62:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for ( long long int i=0; i<kr.size(); i++){
      |                           ~^~~~~~~~~~
plan.cpp:64:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for ( long long int j=0; j<g [x].size(); j++){
      |                            ~^~~~~~~~~~~~~

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