Submission #492354

#	Time	Username	Problem	Language	Result	Execution time	Memory
492354		hohohaha	Evacuation plan (IZhO18_plan)	C++14	100 / 100	663 ms	70824 KiB

plan

// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("output.out","w",stdout);
   fastio();
   
   int tc = 1;
   
//   cin >> tc; 
   
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

const ld pi = 4 * atan(1.0), eps = 1e-9;

#define int long long
const int maxn = 100000 + 5, mod = 924844033; 

const int inf = LLONG_MAX / 2; 

int n, m, k, q; 

int dis[maxn]; 

vector<ii> g[maxn]; 

int rt[maxn]; 

set<int> S[maxn]; 
vector<int> T[maxn]; 

vector<pair<int, ii> > E; 

int ans[maxn]; 

void join(int u, int v, int w) { 
	if(rt[u] == rt[v]) return; 
	
	u = rt[u], v = rt[v]; 
	
	if(S[u].size() + T[u].size() < S[v].size() + T[v].size()) { 
		swap(u, v); 
	}
	
	for(auto id: S[v]) { 
		if(S[u].count(id)) 	ans[id] = w, S[u].erase(id); 
		else S[u].em(id); 
	}
	
	for(int id: T[v]) { 
	 	T[u].eb(id);
	 	rt[id] = u; 
	 }
}

void solve() {
	cin >> n >> m;
	
	fori(i,1, m) { 
		int u, v, l; 
		cin >> u >> v >> l; 
		g[u].eb(v, l); 
		g[v].eb(u,l);
	}
	
	fill(all(dis), inf); 
	
	priority_queue<ii, vector<ii> , greater<ii> > q; 
	
	cin >> k; 
	
	fori(i, 1, k) { 
		int id; cin >> id; 
		dis[id] = 0; 
		q.em(0, id); 
	}
	
	cin>> ::q; 
	
	fori(i, 1, ::q) { 
		int u, v; 
		cin >> u >> v; 
		S[u].em(i); 
		S[v].em(i); 
	}
	
	while(q.size()) { 
		int d = q.top().fi, u = q.top().se; 
		
		q.om(); 
		
		if(d != dis[u]) continue; 
		
//		cout << u << sp << dis[u] << "KKKK\n"; 
		
		for(ii v: g[u]) { 
			if(dis[v.fi] > dis[u] + v.se) { 
				dis[v.fi] = dis[u] + v.se; 
				q.em(dis[v.fi], v.fi); 
			}
		}
	}
	
	fori(i, 1, n) { 
		for(ii v : g[i]) {
			int j = v.fi; 
			if(j < i) continue; 
			
//			cout << i << sp << j << sp << min(dis[i],dis[j]) << endl;
			
			E.eb(min(dis[i], dis[j]), ii(i, j)); 
		}
	}
	
	sort(all(E)); 
	
	reverse(all(E)); 
	
	fori(i,1, n) rt[i] = i, T[i].eb(i); 
	
	fill(all(ans), inf);
	
	for(auto t: E) { 
		int d= t.fi, u = t.se.fi, v = t.se.se; 
		
//		cout<< d << sp <<u << sp << v << endl << endl;
		
		join(u, v, d); 
	}
	
	fori(i, 1, ::q) { 
		cout << ans[i] << endl;; 
	}
	
//	fori(i, 1, n ) { 
//		cout << rt[i] << "\\"; for(int x: S[i]) cout << x << sp; 
//		cout << endl;
//	}
}

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