Submission #671639

#	Time	Username	Problem	Language	Result	Execution time	Memory
671639		Baytoro	Evacuation plan (IZhO18_plan)	C++17	100 / 100	527 ms	74168 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e18,mod=1e9+7;
struct edge{
	int a,b,c;
};
vector<pair<int,int>> g[100005],ed[100005];
vector<int> dist(100005,INF),p(100005),sz(100005),depth(100005);
int f(int x){
	if(p[x]==x) return x;
	return p[x]=f(p[x]);
}
void un(int a, int b){
	int ta=a,tb=b;
	int cost=min(dist[a],dist[b]);
	a=f(a),b=f(b);
	if(a==b) return;
	if(sz[a]>sz[b]) swap(a,b);
	//cout<<ta<<' '<<tb<<endl;
	ed[ta].pb({tb,cost});
	ed[tb].pb({ta,cost});
	p[a]=b;
	sz[b]+=sz[a];
}
int P[100005][21],bj[100005][21];
void dfs(int x, int par){
	P[x][0]=par;
	bj[x][0]=dist[x];
	depth[x]=depth[par]+1;
	for(auto it: ed[x]){
		if(it.fr==par) continue;
		dfs(it.fr,x);
	}
}
int lca(int a, int b){
	if(depth[a]<depth[b]) swap(a,b);
	int k=depth[a]-depth[b];
	int res=INF;
	for(int l=20;l>=0;l--){
		if(k&(1<<l)){
			res=min(res,bj[a][l]);
			a=P[a][l];
		}
	}
	if(a==b) return min(res,dist[a]);
	for(int l=20;l>=0;l--){
		if(P[a][l]!=P[b][l]){
			res=min(res,bj[a][l]);
			res=min(res,bj[b][l]);
			a=P[a][l];
			b=P[b][l];
		}
	}
	res=min(res,bj[a][1]);
	res=min(res,bj[b][1]);
	return res;
}
int n,m;
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
		sz[i]=1;
	}
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		g[a].pb({b,c});
		g[b].pb({a,c});
	}
	int k;cin>>k;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> dq;
	for(int i=0;i<k;i++){
		int x;
		cin>>x;
		dq.push({0,x});
		dist[x]=0;
	}
	while(!dq.empty()){
		pair<int,int> a=dq.top();
		dq.pop();
		if(dist[a.sc]<a.fr) continue;
		for(auto it: g[a.sc]){
			if(dist[it.fr]<=it.sc+a.fr) continue;
			else{
				dist[it.fr]=it.sc+a.fr;
				dq.push({dist[it.fr],it.fr});
			}
		}
	}
	vector<pair<int,int>> vec;
	for(int i=1;i<=n;i++){
		vec.pb({dist[i],i});
	}
	sort(rall(vec));
	vector<int> used(n+1);
	for(int i=0;i<n;i++){
		used[vec[i].sc]=1;
		for(auto it: g[vec[i].sc]){
			if(used[it.fr])
				un(vec[i].sc,it.fr);
		}
	}
	dfs(1,0);
	for(int i=1;i<21;i++){
		for(int l=1;l<=n;l++){
			P[l][i]=P[P[l][i-1]][i-1];
			bj[l][i]=min(bj[l][i-1],bj[P[l][i-1]][i-1]);
		}
	}
	/*for(int i=1;i<=n;i++){
		for(int l=0;l<21;l++)
			cout<<bj[i][l]<<' ';
		cout<<endl;
	}*/
	int q;
	cin>>q;
	while(q--){
		int a,b;cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
}
main(){
	ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message (stderr)

plan.cpp:134:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  134 | main(){
      | ^~~~
plan.cpp: In function 'void fopn(std::string)':
plan.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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