제출 #1114627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114627		adiyer	Evacuation plan (IZhO18_plan)	C++17	100 / 100	919 ms	75712 KiB

plan

#include <bits/stdc++.h>

#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) (x.begin(), x.end())
#define pb push_back

#define int long long

typedef long long ll;

using namespace std;

const int N = 1e5 + 11;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 11;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll n, m, k, Q;
ll p[N], d[N], qu[N], qv[N];

map < pair < ll, ll >, ll > ans;

vector < pair < ll, ll > > g[N], scan;

set < ll > cmp[N], ver[N];

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

void unite(ll a, ll b, ll w){
	a = get(a), b = get(b);
	if(a == b) return;
	if(cmp[a].size() > cmp[b].size()) swap(a, b);
	for(auto x : cmp[a]){
		vector < ll > del;
		for(auto it : ver[x]){
			if(cmp[b].find(it) != cmp[b].end()){
				ans[{it, x}] = ans[{x, it}] = w;
				del.pb(it);
			}
		}
		for(ll pt : del) ver[x].erase(pt);
	}
	for(auto x : cmp[a]) cmp[b].insert(x);
	cmp[a].clear();
	p[a] = b;
}

void solve(){
	cin >> n >> m;
	for(ll i = 1; i <= n; i++) p[i] = i, d[i] = inf, cmp[i].insert(i);
	for(ll i = 1, u, v, w; i <= m; i++){
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	set < pair < ll, ll > > q;
	cin >> k;
	for(ll i = 1, v; i <= k; i++){
		cin >> v;
		d[v] = 0;
		q.insert({d[v], v});
	}
	while(!q.empty()){
		ll v = (q.begin() -> second);
		q.erase(q.begin());
		for(auto [u, w] : g[v]){
			if(d[v] + w < d[u]){
				q.erase({d[u], u});
				d[u] = d[v] + w;
				q.insert({d[u], u});
			}
		}
	}
	cin >> Q;
	for(ll i = 1; i <= Q; i++){
		cin >> qv[i] >> qu[i];
		ver[qv[i]].insert(qu[i]);
		ver[qu[i]].insert(qv[i]);
	}
	for(ll i = 1; i <= n; i++) scan.pb({d[i], i});
	sort(scan.begin(), scan.end());
	reverse(scan.begin(), scan.end());
	for(auto [val, v] : scan)
		for(auto [u, w] : g[v])
			if(d[u] >= val && get(u) != get(v))
				unite(u, v, val);
	for(ll i = 1; i <= Q; i++){
		cout << ans[{qu[i], qv[i]}] << '\n';
	}
}

const bool Cases = 0;

signed main(){
	adiyer();
	int CS = 1;
	if(Cases) cin >> CS;
	while(CS--) solve();
}

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