Submission #334430

#	Time	Username	Problem	Language	Result	Execution time	Memory
334430		Kerim	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1370 ms	34252 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];
int sz[MAXN],ans[MAXN],vis[MAXN];
int L[MAXN],R[MAXN],can[MAXN];
vector<PII>adj[MAXN];
vector<int>tmp[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){
	if((x=tap(x))==(y=tap(y)))
		return;
	if(sz[x]<sz[y])swap(x,y);
	sz[x]+=sz[y];
	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);
		query[i]=mp(u,v);
		L[i]=1,R[i]=n;
    }
    for(int i=1;i<=n;i++)
    	id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++)
    	can[i]=dis[id[i]];
    for(int j=0;j<18;j++){
    	for(int i=1;i<=n;i++)
    		ata[i]=i,sz[i]=1,vis[i]=0;
    	for(int i=1;i<=qq;i++)
    		if(L[i]!=R[i]){
	    		int mid=(L[i]+R[i]+1)>>1;
				tmp[mid].pb(i);
	    	}
	    for(int i=n;i>=1;i--){
	    	vis[id[i]]=1;
			tr(it,adj[id[i]])	
				if(vis[it->ff])
					merge(it->ff,id[i]);
			tr(it,tmp[i]){
				if(tap(query[*it].ff)==tap(query[*it].ss))
					L[*it]=i;
				else
					R[*it]=i-1;
			}
			tmp[i].clear();		
	    }
	}
	for(int i=1;i<=qq;i++)
		printf("%d\n",can[L[i]]);
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
plan.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     scanf("%d",&k);
      |     ~~~~~^~~~~~~~~
plan.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
plan.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d",&qq);
      |     ~~~~~^~~~~~~~~~
plan.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   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