Submission #168566

#	Time	Username	Problem	Language	Result	Execution time	Memory
168566		GioChkhaidze	Evacuation plan (IZhO18_plan)	C++14	100 / 100	679 ms	27716 KiB

plan

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=1e5+5;

int n,m,k,q;
bool f[N];
int p[N],d[N],tot[N],ANS[N];
priority_queue < pair < int , int > > Q;
vector < pair < int , int > > s,v[N],Query[N];

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

void Uni(int a,int b,int c) {
	a=P(a),b=P(b);
	if (Query[a].size()+tot[a]<Query[b].size()+tot[b]) swap(a,b);
	for (int i=0; i<Query[b].size(); i++) {
		if (P(Query[b][i].F)==P(a)) ANS[Query[b][i].S]=c;
			else Query[a].push_back(Query[b][i]);
	}
	p[b]=a;
	tot[a]+=tot[b];
}

main () { 
	scanf("%d%d",&n,&m);
	
	for (int i=1; i<=m; i++) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	
	scanf("%d",&k);
	
	for (int i=1; i<=n; i++)
		d[i]=1e9;
	
	for (int i=1; i<=k; i++) {
		int x;
		scanf("%d",&x);
		d[x]=0;
	}
	
	for (int i=1; i<=n; i++) 
		Q.push({-d[i],i});
		
	while (!Q.empty()) {
		int x=Q.top().S;
		Q.pop();
		if (f[x]) continue ;
		f[x]=1;
		for (int i=0; i<v[x].size(); i++) {
			int to=v[x][i].F,cost=v[x][i].S;
			if (!f[to] && d[x]+cost<d[to]) {
				d[to]=d[x]+cost;
				Q.push({-d[to],to});
			}
		}
	}

	for (int i=1; i<=n; i++) 
		s.push_back({d[i],i});
	
	sort(s.begin(),s.end());
	reverse(s.begin(),s.end());
	
	scanf("%d",&q);
	
	for (int i=1; i<=q; i++) {
		int a,b;
		scanf("%d%d",&a,&b);
		Query[a].push_back({b,i});		
		Query[b].push_back({a,i});		
	}
	
	for (int i=1; i<=n; i++) 
		p[i]=i,f[i]=0,tot[i]=1;
	
	for (int i=0; i<s.size(); i++) {
		int x=s[i].S,cost=s[i].F;
		f[x]=1;
		for (int i=0; i<v[x].size(); i++) {
			int to=v[x][i].F;
			if (f[to]) 
				if (P(x)!=P(to)) 
					Uni(x,to,cost);
		}
	}
	
	for (int i=1; i<=q; i++) 
		printf("%d\n",ANS[i]);	
}

Compilation message (stderr)

plan.cpp: In function 'void Uni(int, int, int)':
plan.cpp:21:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<Query[b].size(); i++) {
                ~^~~~~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:29:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
plan.cpp: In function 'int main()':
plan.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~
plan.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) {
                ~^~~~~~~~~
plan.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~
plan.cpp:30: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:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
  ~~~~~^~~~~~~~~
plan.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
plan.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
plan.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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