Submission #201645

#	Time	Username	Problem	Language	Result	Execution time	Memory
201645		Gurban	Evacuation plan (IZhO18_plan)	C++14	29 / 100	775 ms	45028 KiB

plan

#include <bits/stdc++.h>
 
#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2
#define pii pair<int,int>
 
using namespace std;
 
int n,m,w,k,t,dis[N],ans,x,y,L[N],sp[N][22],vis[N],mn[N][22];
priority_queue <pii,vector <pii>,greater<pii>> q;
vector <pii> E[N];
vector <int> EG[N];
 
void prim(){
	memset(vis,0,sizeof(vis));
	priority_queue <pii> p;
	p.push({dis[1],1});
	while(!p.empty()){
		y = p.top().ss;
		p.pop();
		if(vis[y]) continue;
		vis[y] = 1;
		EG[sp[y][0]].pb(y);
		for(auto i : E[y]){
			if(vis[i.ff] == 0){
				p.push({dis[i.ff],i.ff});
				sp[i.ff][0] = y;
			}
		}
	}
}
 
void dfs(int nd){
	for(auto i : EG[nd]){
		L[i] = L[nd] + 1;
		mn[i][0] = min(dis[i],dis[nd]);
		dfs(i);
	}
}
 
int LCA(int x,int y){
	ans = min(dis[x],dis[y]);
	if(L[x] < L[y]) swap(x,y);
	
	for(int i = 20;i >= 0;i--)
		if(L[sp[x][i]] >= L[y] and sp[x][i]){
			ans = min(mn[x][i],ans);
			x = sp[x][i];
		}
	
	if(x == y) return x;
	
	for(int i = 20;i >= 0;i--)
		if(sp[x][i] != sp[y][i] and sp[x][i] and sp[y][i]){
			ans = min(ans,min(mn[y][i],mn[x][i]));
			x = sp[x][i],y = sp[y][i];
		}
	ans = min(ans,dis[sp[x][0]]);
	return sp[x][0];
}
 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		scanf("%d%d%d",&x,&y,&w);
		E[x].pb({y,w});
		E[y].pb({x,w});
	}
	for(int i = 1;i <= n;i++) dis[i] = mn[i][0] = inf;
	scanf("%d",&k);
	for(int i = 1;i <= k;i++){
		scanf("%d",&x);
		dis[x] = 0;
		q.push({0,x});
	}
	while(!q.empty()){
		x = q.top().ss;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(auto i : E[x]){
			if(dis[i.ff] > dis[x] + i.ss){
				dis[i.ff] = dis[x] + i.ss;
				q.push({dis[i.ff],i.ff});
			}
		}
	}
	prim();
	dfs(1);
	int lg = log2(n);
	for(int i = 1;i <= lg;i++){
		for(int j = 1;j <= n;j++){
			sp[j][i] = sp[sp[j][i - 1]][i - 1];
			mn[j][i] = min(mn[j][i - 1],mn[sp[j][i - 1]][i - 1]);
		}
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&x,&y);
		LCA(x,y);
		printf("%d\n",ans);
	}
}
/*
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:69: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:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
  ~~~~~^~~~~~~~~
plan.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
plan.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
plan.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

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