Submission #42528

#	Time	Username	Problem	Language	Result	Execution time	Memory
42528		wzy	Evacuation plan (IZhO18_plan)	C++11	0 / 100	698 ms	83208 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define F first
#define int long long
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
int n , m , k , d[100005] , pai[100005] , peso[100005] , fn[100005] , sparse[100005][22] , custo[100005] , anc[100005][22] , h[100005];
vector<pii> adj[100005];
struct edges{
	int x , y, z;
};


bool cmp(edges a , edges b){
	return a.z > b.z;
}

void pre(int i , int j){
	if(i == j) h[i] = 0;
	for(int y = 0 ; y < adj[i].size();y++){
		pii v = adj[i][y];
		if(v.S == j) continue;
		fn[v.S] = i;
		custo[v.S] = v.F;
		h[v.S] = h[i] + 1;
		pre(v.S , i);
	}
}

int fd(int x){ return pai[x] == x ? x : pai[x] = fd(pai[x]);}

void join(int u , int v){
	u = fd(u) , v = fd(v);
	if(peso[u] > peso[v]) swap(u,v);
	pai[u] = v, peso[v] += peso[u] + 1;
}


int query(int x , int y){
	if(h[x] < h[y]) swap(x,y);
	int ansj = (int) 1e18;
	for(int i = 21 ; i >= 0 ; i--){
		while(h[x]  >= h[y] + (1LL<<i)){
			ansj = min(ansj , sparse[x][i]);
			x = anc[x][i];
		}
	}
	if(x == y) return ansj;
	for(int i = 21 ; i >= 0 ; i--){
		if(anc[x][i] != anc[y][i] && anc[x][i] != -1){
			ansj = min(ansj , sparse[x][i]);
			ansj = min(ansj , sparse[y][i]);
			x = anc[x][i] , y = anc[y][i];
		}
	}
	ansj = min(ansj , sparse[x][0]);
	ansj = min(ansj , sparse[y][0]);
	return ansj;
}

int32_t main(){
	scanf("%lld%lld" , &n,  &m);
	vector<edges> v;
	for(int i = 0 ; i <n;i++){
		pai[i] = i , peso[i] = 0 , d[i] = (int) 1e18;
	}
	for(int i = 0 ; i < m ; i++){
		int x,y,z;
		scanf("%lld%lld%lld" , &x , &y , &z);
		x--, y--;
		v.pb({x,y,z});
		adj[x].pb(pii(z,y));
		adj[y].pb(pii(z,x));
	}
	scanf("%lld" , &k);
	priority_queue<pii , vector<pii> , greater<pii> > pq;
	for(int i = 0 ; i < k ; i++) {
		int x;
		scanf("%lld" , &x);
		x--;
		d[x] = 0;
		pq.push(pii(0,x));
	}
	while(!pq.empty()){
		pii u = pq.top();
		pq.pop();
		if(d[u.S] != u.F) continue;
		for(int j = 0 ; j < adj[u.S].size();j++){
			pii v = adj[u.S][j];
			if(d[v.S] > v.F + u.F){
				d[v.S] = v.F + u.F;
				pq.push(pii(d[v.S] , v.S));
			}
		}
	}
	for(int i = 0 ; i < m ; i++){
		v[i].z = min(d[v[i].x] , d[v[i].y]);
		adj[v[i].x].clear();
		adj[v[i].y].clear();
	}
	sort(v.begin() , v.end() , cmp);
	for(int i = 0 ; i <m;i++){
		if(fd(v[i].x) != fd(v[i].y)){
			join(v[i].x , v[i].y);
			adj[v[i].x].pb(pii(v[i].z , v[i].y));
			adj[v[i].y].pb(pii(v[i].z , v[i].x));
		}
	}

	for(int i = 0 ; i < 100005 ; i++)
		for(int j = 0 ; j < 22 ; j++) anc[i][j] = -1 , sparse[i][j] = 1000000009;
	memset(fn , -1 , sizeof fn);
	pre(0 , 0);
	for(int i = 0 ; i < 100005 ; i++){
		if(fn[i] != -1) anc[i][0] = fn[i] , sparse[i][0] = custo[i];
	}
	for(int j = 1; j < 22 ; j++){
		for(int i = 0 ; i < 100005;i++){
			if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j-1]][j-1] , sparse[i][j] = min(sparse[i][j] , min(sparse[i][j-1] , custo[anc[i][j-1]]));
		}
	}
	int q;
	scanf("%lld" , &q);
	while(q--){
		int x,y;
		scanf("%lld%lld" , &x , &y);
		x-- ,y--;
		printf("%lld\n" , query(x,y));
	}
}

Compilation message (stderr)

plan.cpp: In function 'void pre(long long int, long long int)':
plan.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int y = 0 ; y < adj[i].size();y++){
                  ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'int32_t main()':
plan.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[u.S].size();j++){
                   ~~^~~~~~~~~~~~~~~~~
plan.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld" , &n,  &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld" , &x , &y , &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &k);
  ~~~~~^~~~~~~~~~~~~
plan.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &x);
   ~~~~~^~~~~~~~~~~~~
plan.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &q);
  ~~~~~^~~~~~~~~~~~~
plan.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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