Submission #334406

#	Time	Username	Problem	Language	Result	Execution time	Memory
334406		Kerim	Evacuation plan (IZhO18_plan)	C++17	100 / 100	840 ms	35396 KiB

plan

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int dis[MAXN],ata[MAXN],id[MAXN],ans[MAXN],vis[MAXN];
vector<PII>adj[MAXN];
set<int>s[MAXN];
PII query[MAXN];
bool cmp(int x,int y){
	return dis[x]>dis[y];	
}
int tap(int x){
	if(ata[x]==x)
		return x;
	return ata[x]=tap(ata[x]);	
}
void merge(int x,int y,int val){
	if((x=tap(x))==(y=tap(y)))
		return;
	if((int)s[x].size()<(int)s[y].size())	
		swap(x,y);
	tr(it,s[y]){
		if(s[x].count(*it))
			ans[*it]=val;
		else
			s[x].insert(*it);
	}s[y].clear();
	ata[y]=x;
}
int main(){
   // freopen("file.in", "r", stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		adj[u].pb(mp(v,w));
		adj[v].pb(mp(u,w));	
    }
    for(int i=1;i<=n;i++)
    	dis[i]=INF;
    int k;
    scanf("%d",&k);
    queue<int>q;
    for(int i=1;i<=k;i++){
    	int x;
		scanf("%d",&x);
		q.push(x);dis[x]=0;	
    }
    while(!q.empty()){
    	int nd=q.front();q.pop();	
    	tr(it,adj[nd])
    		if(umin(dis[it->ff],dis[nd]+it->ss))
    			q.push(it->ff);
    }
    int qq;
    scanf("%d",&qq);
    for(int i=1;i<=qq;i++){
    	int u,v;
		scanf("%d%d",&u,&v);
		s[u].insert(i);
		s[v].insert(i);
		query[i]=mp(u,v);
    }
    for(int i=1;i<=n;i++)
    	ata[i]=id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++){
    	vis[id[i]]=1;
		tr(it,adj[id[i]])	
			if(vis[it->ff])
				merge(it->ff,id[i],dis[id[i]]);
    }
    for(int i=1;i<=qq;i++)
    	printf("%d\n",ans[i]);
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   89 |     for(int i=1;i<=qq;i++)
      |     ^~~
plan.cpp:91:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   91 |  return 0;
      |  ^~~~~~
plan.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     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]
   51 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     scanf("%d",&k);
      |     ~~~~~^~~~~~~~~
plan.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
plan.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d",&qq);
      |     ~~~~~^~~~~~~~~~
plan.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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