Submission #201631

#	Time	Username	Problem	Language	Result	Execution time	Memory
201631		Gurban	Evacuation plan (IZhO18_plan)	C++14	100 / 100	810 ms	56672 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],par[N];
priority_queue <pii,vector <pii>,greater<pii>> q;
vector <pii> E[N];
vector <int> EG[N];
vector <pair<int,pii>> adj;

int ata(int x){
	if(x == par[x]) return x;
	
	return par[x] = ata(par[x]);
}

bool isS(int x,int y){
	x = ata(x),y = ata(y);
	if(x == y) return 1;
	
	return 0;
}

void un(int x,int y){
	x = ata(x),y = ata(y);
	par[y] = x;
}

void sol(){
	for(auto i : adj){
		w = i.ff,x = i.ss.ff,y = i.ss.ss;
		if(!isS(x,y)){
			EG[y].pb(x);
			EG[x].pb(y);
			un(x,y);
		}
	}
}

void dfs(int nd,int pr){
	L[nd] = L[pr] + 1;
	sp[nd][0] = pr;
	mn[nd][0] = min(dis[nd],dis[pr]);
	for(auto i : EG[nd]){
		if(i != pr){
			dfs(i,nd);
		}
	}
}

void 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;
	
	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;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		scanf("%d%d%d",&x,&y,&w);
		adj.pb({0,{x,y}});
		E[x].pb({y,w});
		E[y].pb({x,w});
	}
	for(int i = 0;i <= n;i++){
		dis[i] = mn[i][0] = inf;
		par[i] = i;
	}
	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});
			}
		}
	}
	for(int i = 0;i < adj.size();i++)
		adj[i].ff = min(dis[adj[i].ss.ff],dis[adj[i].ss.ss]);
	sort(adj.begin(),adj.end());
	reverse(adj.begin(),adj.end());
	sol();
	dfs(1,0);
	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:112:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < adj.size();i++)
                ~~^~~~~~~~~~~~
plan.cpp:83: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:85: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:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&k);
  ~~~~~^~~~~~~~~
plan.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
plan.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
plan.cpp:127: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: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46