제출 #151664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151664		nvmdava	Evacuation plan (IZhO18_plan)	C++17	100 / 100	626 ms	37992 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define N 100002
#define ff first
#define ss second
#define ll long long
 
int d[N], n, m;
vector<pair<int, int> > adj[N];
 
priority_queue<pair<int, int> > pq;
vector<int> dis;
 
vector<pair<int, int> > plist[N];
bool in[N];
int p[N];
vector<int> group[N];
 
int find(int v){
	return v == p[v] ? v : p[v] = find(p[v]);
}
 
void merge(int v, int u, int dre){
	v = find(v);
	u = find(u);
	if(v == u) return;
	if(group[v].size() > group[u].size()) swap(v, u);
	p[v] = u;
 
	for(int& x : group[v]){
		while(plist[x].back().ff == dre)
			plist[x].pop_back();
		plist[x].push_back({dre, u});
		group[u].push_back(x);
	}
	group[v].clear();
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	 
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	memset(d, 0x3f, sizeof d);
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		plist[i].push_back({0x3f3f3f3f, i});
		p[i] = i;
		group[i].push_back(i);
	}
 
	while(m--){
		int v, u, w;
		cin>>v>>u>>w;
		adj[v].push_back({u, w});
		adj[u].push_back({v, w});
	}
 
	cin>>m;
	while(m--){
		int v;
		cin>>v;
		d[v] = 0;
		pq.push({0, v});
	}
 
	while(!pq.empty()){
		int v = pq.top().ss;
		int dd = pq.top().ff;
		pq.pop();
		if(dd != -d[v]) continue;
		for(auto& x : adj[v]){
			if(d[x.ff] > x.ss - dd){
				d[x.ff] = x.ss - dd;
				pq.push({-d[x.ff], x.ff});
			}
		}
	}
 
	for(int i = 1; i <= n; i++)
		dis.push_back(i);
	
	sort(dis.begin(), dis.end(), [](const int& lhs, const int& rhs){
		return d[lhs] > d[rhs];
	});
 
	for(auto& x : dis){
		in[x] = 1;
		for(auto& y : adj[x])
			if(in[y.ff]) merge(x, y.ff, d[x]);
	}
 
	cin>>m;
	while(m--){
		int v, u;
		cin>>v>>u;
		int i1 = plist[v].size() - 1, i2 = plist[u].size() - 1;
		while(plist[v][i1].ss == plist[u][i2].ss){
			i1--; i2--;
		}
		i1++;
		i2++;
		
		cout<<min(plist[v][i1].ff, plist[u][i2].ff)<<'\n';
	}
}

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