Submission #1171299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171299		ZeroCool	Evacuation plan (IZhO18_plan)	C++20	100 / 100	658 ms	44952 KiB

plan

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

const int N = 5e4 + 20;
const int K = 469;
const int LOG = 26;
const int INF = 1e9;	
int MOD = 998244353;

void chmin(int &x,int y){x = min(x, y);}
void chmax(int &x,int y){x = max(x, y);}


struct DSU{
    vector<int> p;

	DSU(int n){
		p.resize(n);
		iota(all(p), 0);
	}

	int fnd(int x){
		if(p[x] == x)return x;
		return p[x] = fnd(p[x]);
	}
	bool upd(int a,int b){
		a = fnd(a);
		b = fnd(b);
		if(a == b)return 0;
		p[a] = b;
		return 1;
	}

	bool qry(int a,int b){
		return fnd(a) == fnd(b);
	}
};

void orz(){
	int n, m;
	cin>>n>>m;
	vector<ar<int, 2> > g[n];
	while(m--){
		int a, b, c;
		cin>>a>>b>>c;
		--a, --b;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	
	bool vis[n] = {0};
	int k;
	cin>>k;
	priority_queue<ar<int, 2> > pq;
	while(k--){
		int x;
		cin>>x;
		--x;
		pq.push({0, x});
	}
	int dst[n];
	while(pq.size()){
		auto [d, x] = pq.top();
		pq.pop();
		if(vis[x])continue;
		vis[x] = 1;
		//cout<<d<<" "<<x<<'\n';
		dst[x] = -d;
		for(auto [u, w]: g[x]){
			if(!vis[u])pq.push({d - w, u });
		}
	}
	//for(int i = 0;i < n;i++)cout<<dst[i]<<" ";
	//out<<'\n';
	vector<int> v;
	for(int i =0;i < n;i++)v.push_back(dst[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	m = v.size();
	vector<int> ind[m];
	for(int i = 0;i < n;i++)ind[lower_bound(all(v), dst[i]) - v.begin()].push_back(i);
	int q;
	cin>>q;
	ar<int, 2> que[q];
	int l[q], r[q];

	for(int i = 0;i < q;i++){
		int a, b;
		cin>>a>>b;
		--a, --b;
		que[i] = {a, b};
		l[i] = -1;
		r[i] = m;
	}
	while(1){
		bool f = 1;
		vector<int> s[m];
		for(int i = 0;i < q;i++){
			if(r[i] - l[i] > 1)f = 0;
			s[(l[i] + r[i]) /2].push_back(i);
		}
		if(f)break;
		DSU dsu(n);
		bool vis[n] = {0};
		for(int i = m - 1;i >= 0;i--){
			for(auto x: ind[i]){
				for(auto [u, w]: g[x]){
					if(vis[u])dsu.upd(u, x);
				}
				vis[x] = 1;
			}
			for(auto j: s[i]){
				if(dsu.qry(que[j][0], que[j][1]))l[j] = i;
				else r[j] = i;
			}
		}
	}
	for(int i = 0;i < q;i++)cout<<v[l[i]]<<'\n';
}	
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	//cin>>t;
	t = 1;
	while(t--)orz();
}
	

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