Submission #379404

#	Time	Username	Problem	Language	Result	Execution time	Memory
379404		PixelCat	Evacuation plan (IZhO18_plan)	C++14	100 / 100	780 ms	82764 KiB

plan

/*                                                       
  /^--^\                                                 
  \____/                                                 
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|*/
//#pragma GCC optimize("O4,unroint-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<ll,ll>;
//using pii=pair<int,int>;
#define int ll //__int128
#define double long double

#define For(i,a,b)  for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1e9+7)
#define INF (int)(1e15)
#define EPS (1e-9)

#ifdef LOCALMEOW
#define debug(...) do{\
	cerr << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
#else
#define debug(...)
#endif
inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng((ull)new char);
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1,now=b;
	while(p){
		if(p&1) ans=ans*now%mod;
		p/=2; now=now*now%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
void minimize(int &a,const int &b) { if(b<a) a=b; }
void maximize(int &a,const int &b) { if(b>a) a=b; }

struct DSU{
	int p[100010];
	void init(int n){
		For(i,1,n) p[i]=i;
	}
	int find(int n){
		if(p[n]==n) return n;
		return p[n]=find(p[n]);
	}
	void uni(int a,int b){
		a=find(a); b=find(b);
		p[a]=b;
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
}dsu;

vector<pair<pii,int>> ed;
int dis[100010];
int dep[100010];
int p[100010][20];
int w[100010][20];
vector<int> gg;

void dijkstra(int n){
	vector<vector<pii>> adj(n+1);
	for(auto &i:ed){
		adj[i.F.F].eb(i.F.S,i.S);
		adj[i.F.S].eb(i.F.F,i.S);
	}
	memset(dis,-1,sizeof(dis));
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(auto &i:gg)
		pq.emplace(0,i);
	while(!pq.empty()){
		int now=pq.top().S;
		int d=pq.top().F;
		pq.pop();
		if(dis[now]!=-1) continue;
		dis[now]=d;
		for(auto &i:adj[now]){
			if(dis[i.F]==-1){
				pq.emplace(i.S+d,i.F);
			}
		}
	}
}

void dfs(int n,int pa,int d,int wt,vector<vector<pii>> &adj){
	dep[n]=d;
	p[n][0]=pa;
	w[n][0]=wt;
	for(auto &i:adj[n]) if(i.F!=pa){
		dfs(i.F,n,d+1,i.S,adj);
	}
}

void buildtree(int n){
	dsu.init(n);
	for(auto &i:ed)
		i.S=min(dis[i.F.F],dis[i.F.S]);
	sort(all(ed),[](pair<pii,int> &a,pair<pii,int> &b){
		return a.S>b.S;
	});
	vector<vector<pii>> tre(n+1);
	for(auto &i:ed) if(!dsu.same(i.F.F,i.F.S)){
		tre[i.F.F].eb(i.F.S,i.S);
		tre[i.F.S].eb(i.F.F,i.S);
		dsu.uni(i.F.F,i.F.S);
	}
	dfs(1,1,1,INF,tre);
}

void buildLCA(int n){
	For(j,1,19) For(i,1,n){
		p[i][j]=p[p[i][j-1]][j-1];
		w[i][j]=min(w[i][j-1],w[p[i][j-1]][j-1]);
	}
}

int askLCA(int a,int b){
	int ans=INF;
	if(dep[a]<dep[b]) swap(a,b);
	Forr(j,19,0) if(dep[p[a][j]]>=dep[b]){
		ans=min(ans,w[a][j]);
		a=p[a][j];
	}
	Forr(j,19,0){
		if(p[a][j]!=p[b][j]){
			ans=min(ans,min(w[a][j],w[b][j]));
			a=p[a][j];
			b=p[b][j];
		}
	}
	if(a!=b){
		ans=min(ans,min(w[a][0],w[b][0]));
	}
	return ans;
}

int32_t main(){
	NYA();
	//shinon >/////<
	int n,m; cin>>n>>m;
	ed.resize(m);
	for(auto &i:ed)
		cin>>i.F.F>>i.F.S>>i.S;
	int k; cin>>k;
	gg.resize(k);
	for(auto &i:gg)
		cin>>i;
	dijkstra(n);
	buildtree(n);
	buildLCA(n);
	int q; cin>>q;
	while(q--){
		int a,b; cin>>a>>b;
		cout<<askLCA(a,b)<<"\n";
	}
	return 0;
}

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