Submission #91011

#	Time	Username	Problem	Language	Result	Execution time	Memory
91011		Scayre	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1122 ms	80428 KiB

plan

//#include <bits/stdc++.h>

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <complex>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define ll long long
#define ld long double
#define ull unsigned ll
#define ioi exit(0);

#define f first
#define s second

#define inf (int)1e9 + 7

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define mp(x,y) make_pair(x,y)

#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)

#define pb push_back
#define ppb pop_back

#define bitcoin __builtin_popcount

#define endl "\n"

#define in(x) insert(x)

#define sz(x) (int)x.size()

#define all(x) x.begin(),x.end()

#define pw2(x) (1<<x) //2^x

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

#define sqr(x) ((x) * 1ll * (x))

using namespace std;

const int N = (int)5e5 + 7, MOD = (int)1e9 + 7;

int n,m;

bool used[N];

int d[N];

vector<pair<int,int> > v[N],new_v[N];

int up[N][24],mn[N][24];

set<pair<int,int> > s;

vector<pair<int,pair<int,int> > > mx;

void dfs1(int x){
	used[x]=1;
	for(int i=0;i<sz(v[x]);i++){
		int to=v[x][i].f;
		v[x][i].s=min(d[x],d[to]);
		if(!used[to]){
			dfs1(to);
		}
	}
}

int nw;

int tin[N],tout[N];

void dfs2(int x){
	used[x]=1;
	for(int i=0;i<sz(v[x]);i++){
		int to=v[x][i].f;
		mx.pb({v[x][i].s,{x,to}});
		if(!used[to]){
			dfs2(to);
		}
	}
}

void dfs3(int x,int p=0){
	nw++;
	tin[x]=nw;
	used[x]=1;
	for(int i=0;i<sz(new_v[x]);i++){
		int to=new_v[x][i].f;
		if(!used[to]){
			dfs3(to,x);
			up[to][0]=x;
			mn[to][0]=new_v[x][i].s;
		}
	}
	tout[x]=nw;
}

int col[N],p[N],rnk[N];

int get(int v){
	if(p[v] == v) return v;
	return p[v] = get(p[v]);
}

void Merge(int u,int v){
	v = get(v);
	u = get(u);
	if(rnk[u] < rnk[v]){
		rnk[v] += rnk[u];
		p[u] = v;
	}
	else{
		rnk[u] += rnk[v];
		p[v] = u;
	}
}

bool ok(int x,int y){
	return tin[x]<=tin[y] and tout[x]>=tout[y];
}

int lca(int x,int y){
	if(ok(x,y))return x;
	if(ok(y,x))return y;
	for(int i=20;i>=0;i--){
		if(up[x][i]!=0 and !ok(up[x][i],y)){
			x=up[x][i];
		}
	}
	return up[x][0];
}

int getm(int x,int y){
	int ct=inf;
	if(x==y)return ct;
	for(int i=20;i>=0;i--){
		if(up[x][i]!=0 and !ok(up[x][i],y)){
			ct=min(ct,mn[x][i]);
			//cout << "NWE" << ' ' << x << ' ' << i << ' ' << mn[x][i] << endl;
			x=up[x][i];
		}
	}
	//cout << x << ' ' << mn[x][0] << endl;
	return min(ct,mn[x][0]);
}

int getmin(int x,int y){
	int z = lca(x,y);
	//cout << z << endl;
	//cout << getm(x,z) << ' ' << getm(y,z) << endl;
	return min(getm(x,z), getm(y,z));
}

int main(){

	#ifdef IOI2019
		freopen ("in.txt", "r", stdin);
	#endif

	NFS

	cin >> n >> m;

	for(int i = 1; i <= n; i++) d[i] = inf;

	for(int i=1;i<=m;i++){
		int x,y,z;
		cin >> x >> y >> z;
		v[x].pb({y,z});
		v[y].pb({x,z});
	}

	cin >> m;

	for(int i=1;i<=m;i++){
		int x;
		cin >> x;
		s.insert({0,x});
		d[x]=0;
	}

	while(!s.empty()){
		int x=(*s.begin()).s;
		s.erase(s.begin());
		for(int i=0;i<sz(v[x]);i++){
			int to=v[x][i].f,w=v[x][i].s;
			if(d[to]>d[x]+w){
				s.erase({d[to],to});
				d[to]=d[x]+w;
				s.insert({d[to],to});
			}
		}
	}

	dfs1(1);

	memset(used,0,sizeof(used));

	dfs2(1);

	sort(all(mx));

	reverse(all(mx));

	for(int i=1;i<=n;i++){
		p[i]=i;
		rnk[i]=1;
	}

	for(int i=0;i<sz(mx);i++){
		int x=mx[i].s.f,y=mx[i].s.s,z=mx[i].f;
		if(get(x)!=get(y)){
			Merge(x,y);
			//cout << x << ' ' << y << ' ' << z << endl;
			//cout << get(x) << ' ' << get(y) << endl;
			//if(x == 5) return 0;
			new_v[x].pb({y,z});
			new_v[y].pb({x,z});
		}
	}

	memset(used,0,sizeof(used));

	dfs3(1);

	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			up[i][j]=up[up[i][j-1]][j-1];
			mn[i][j]=min(mn[i][j-1],mn[up[i][j-1]][j-1]);
		}
	}

	cin >> m;

	for(int i=1;i<=m;i++){
		int x,y;
		cin >> x >> y;
		cout << getmin(x,y) << endl;
	}

	#ifdef IOI2019
		cout << "\nTime Elapsed : " << clock () * 1.0 / CLOCKS_PER_SEC << endl;
	#endif

	ioi
}

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