Submission #927139

#	Time	Username	Problem	Language	Result	Execution time	Memory
927139		Gromp15	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	2016 ms	15568 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	int n, m;
	cin >> n >> m;
	int S, T, U, V;
	cin >> S >> T >> U >> V;
	vector<vector<ar<int, 2>>> adj(n+1);
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		adj[x].push_back({y, w});
		adj[y].push_back({x, w});
	}
	auto cost = [&](int sx) -> vector<ll> {
		vector<ll> d(n+1, 1e18);
		priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> q;
		q.push({0, sx});
		d[sx] = 0;
		while (q.size()) {
			auto [weight, v] = q.top(); q.pop();
			if (weight != d[v]) continue;
			for (auto [u, w] : adj[v]) {
				if (ckmin(d[u], d[v] + w)) {
					q.push({d[u], u});
				}
			}
		}
		return d;
	};
	vector<ll> ds(cost(S)), dt(cost(T)), du(cost(U)), dv(cost(V));
	ll ans = 1e18, bst = ds[T];
	vector<int> o1(n), o2(n);
	iota(all(o1), 1), iota(all(o2), 1);
	sort(all(o1), [&](int x, int y) { return ds[x] < ds[y]; });
	sort(all(o2), [&](int x, int y) { return dt[x] < dt[y]; });
	unsigned long long r1[n+1], r2[n+1];
	for (int i = 1; i <= n; i += 64) {
		memset(r1, 0, sizeof(r1));
		memset(r2, 0, sizeof(r2));
		vector<int> each;
		for (int j = i; j <= min(i+63, n); j++) {
			each.push_back(j);
		}
		const int N = sz(each);
		sort(all(each), [&](int x, int y) { return dv[x] < dv[y]; });
		vector<int> where(N);
		for (int j = 0; j < N; j++) {
			where[each[j] - i] = j;
		}
		for (int v : o1) { // v --> s
			if (ds[v] + dt[v] != bst) continue;
			if (v >= i && v < i + 64) r1[v] |= 1ULL << where[v - i];
			if (r1[v]) {
				for (const auto &[u, w] : adj[v]) {
					if (dt[u] + w + ds[v] == bst) r1[u] |= r1[v];
				}
			}
		}
		for (int v : o2) {
			if (ds[v] + dt[v] != bst) continue;
			if (v >= i && v < i + 64) r2[v] |= 1ULL << where[v - i];
			if (r2[v]) {
				for (const auto &[u, w] : adj[v]) {
					if (ds[u] + w + dt[v] == bst) r2[u] |= r2[v];
				}
			}
		}
		for (int j = 1; j <= n; j++) if (r1[j] | r2[j]) {
			int go = __builtin_ctzll(r1[j] | r2[j]);
			ckmin(ans, du[j] + dv[each[go]]);
		}
	}
	cout << min(ans, du[V]) << '\n';
		
	
 
 
 
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45