Submission #379348

#	Time	Username	Problem	Language	Result	Execution time	Memory
379348		fhvirus	Evacuation plan (IZhO18_plan)	C++17	100 / 100	570 ms	40044 KiB

plan

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
inline ll cdiv(ll x,ll m){return x/m+(x%m?(x<0)^(m>0):0);}
#ifdef OWO
#define safe cerr<<"\033[1;32m"<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<" JIZZ\033[0m\n"
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
#else
#pragma GCC optimize("Ofast")
#define safe ((void)0)
#define debug(...) ((void)0)
#endif
const ll inf = 1e9, INF = 4e18;
const int N = 1e5 + 225;
int n, m, q;
vector<pii> adj[N];
int dis[N], ans[N];

vector<pii> qs[N];

struct dsu{
	vector<int> p;
	vector<vector<tuple<int, int, int>>> q;
	dsu(int n){
		p.resize(n + 1); iota(AI(p), 0);
		q.resize(n + 1);
		FOO(i,1,n) for(auto [v, id]: qs[i])
			q[i].pb(i, v, id);
	}
	int F(int u){ return u == p[u] ? u : p[u] = F(p[u]);}
	void M(int a, int b, int w){
		a = F(a), b = F(b);
		if(a == b) return;
		if(q[a].size() < q[b].size()) swap(a, b);
		p[b] = a;
		for(auto [s, t, id]: q[b]){
			if(ans[id]) continue;
			if(F(s) == F(t)) ans[id] = w;
			else q[a].pb(s, t, id);
		}
	}
};

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int _ = 0, a, b, w; _ < m; ++_){
		cin >> a >> b >> w;
		adj[a].pb(b, w);
		adj[b].pb(a, w);
	}

{	// Dijkstra
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	auto upd = [&pq](int u, int d){
		if(chmin(dis[u], d))
			pq.emplace(dis[u], u);
	};
	fill(dis, dis + n + 1, inf);

	int k; cin >> k;
	for(int x; k; --k){
		cin >> x;
		upd(x, 0);
	}

	while(!pq.empty()){
		auto [d, u] = pq.top(); pq.pop();
		if(dis[u] < d) continue;
		for(auto [v, w]: adj[u])
			upd(v, d + w);
	}
}

	cin >> q;
	for(int i = 0, s, t; i < q; ++i){
		cin >> s >> t;
		qs[s].pb(t, i);
		qs[t].pb(s, i);
	}

	vector<int> ord(n); iota(AI(ord), 1);
	sort(AI(ord), [](int a, int b){
		return dis[a] > dis[b];
	});

	dsu D(n + 1);

	for(int u: ord){
		for(auto [v, _]: adj[u])
			if(dis[v] >= dis[u])
				D.M(u, v, dis[u]);
	}
	
	for(int i = 0; i < q; ++i)
		cout << ans[i] << '\n';

	return 0;
}

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