Submission #885398

#	Time	Username	Problem	Language	Result	Execution time	Memory
885398		jcelin	Evacuation plan (IZhO18_plan)	C++14	100 / 100	818 ms	77348 KiB

plan

#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define msi multiset<int>
#define si set<int>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 1e8 + 7;
const ll INF = 1e18 + 7;
const int logo = 30;
const int MAXN = 1e6 + 2;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct uf{
	int par[MAXN], sz[MAXN];
	
	void init(int n){
		for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1;
	}
	
	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	
	void unite(int a, int b){
		a = find(a), b = find(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
	}
	
	bool query(int a, int b){
		return find(a) == find(b);
	}
}uf;

int lo[MAXN], hi[MAXN], dis[MAXN], cj, n, m, q, st[MAXN], en[MAXN], ans[MAXN];
vii g[MAXN];
vector<pair<int, ii>> brid;
vi qs;

bool cmp(int a, int b){
	return lo[a] + hi[a] > lo[b] + hi[b];
}

void paralelni(){
	sort(all(qs), cmp);
	cj = 0;
	uf.init(n);
	for(auto &x : qs){
		if(lo[x] > hi[x]) continue;
		int mid = (lo[x] + hi[x]) / 2;
		while(cj < (int)brid.size() and brid[cj].X >= mid) uf.unite(brid[cj].Y.X, brid[cj].Y.Y), cj++;
		
		if(uf.query(st[x], en[x])) lo[x] = mid + 1, ans[x] = mid;
		else hi[x] = mid - 1;
	}
}

void dijkstra(){
	set<ii> s;
	for(int i=1; i<=n; i++) s.insert({dis[i], i});
	while(!s.empty()){
		ii cur = *s.begin();
		s.erase(s.begin());
		int u = cur.Y, d = cur.X;
		for(auto &x : g[u]){
			int nd = d + x.Y;
			if(nd < dis[x.X]){
				s.erase({dis[x.X], x.X});
				dis[x.X] = nd;
				s.insert({dis[x.X], x.X});
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		for(auto &x : g[i]) if(dis[i] <= dis[x.X]) brid.PB({dis[i], {i, x.X}});
	}
	sort(all(brid));
	reverse(all(brid));
	//for(auto &x : brid) cout << x.X <<  " ( " << x.Y.X << " " << x.Y.Y << " )\n"; 
}

void solve(){
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int a, b, w;
		cin >> a >> b >> w;
		g[a].PB({b, w});
		g[b].PB({a, w});
	}
	
	int k;
	cin >> k;
	for(int i=1; i<=n; i++) dis[i] = inf;
	for(int i=1, x; i<=k; i++) cin >> x, dis[x] = 0;
	dijkstra();
	
	cin >> q;
	for(int i=0; i<q; i++){
		cin >> st[i] >> en[i];
		lo[i] = 0, hi[i] = inf, ans[i] = inf;
		qs.PB(i);
	}

	for(int i=0; i<30; i++) paralelni();
	
	for(int i=0; i<q; i++) cout << ans[i] << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}

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