Submission #1137019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137019		nuutsnoynton	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	223 ms	22188 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll > ;
const ll N = 2e5 + 2;

ll d_1[N], d_2[N];
vector < pll > adj[N];
int main() {
	ll r, x, y, i, s,can, X, Y, lo, hi, mid, n, j, ans, t, e, k, m, st, fn, cost, c;
	
	cin >> n >> m;
	
	cin >> st >> fn >> cost >> k;
	
	for (i = 1; i <= m; i++) {
		cin >> x >> y >> c;
		adj[x].push_back({y, c});
		adj[y].push_back({x, c});
	}
	priority_queue < pll , vector < pll > , greater < pll > > pq;
	for (i = 1; i <= n; i ++) d_1[i] = 1e18;
	d_1[st] = 0;
	pq.push({0, st});
	
	while ( !pq.empty()) {
		x = pq.top().second;
		s = pq.top().first;
		pq.pop();
		if ( d_1[x] != s) continue;
		for ( pll P : adj[x]) {
			y = P.first;
			c = P.second;
			if( d_1[y] > d_1[x] + c) {
				d_1[y] = d_1[x] + c;
				pq.push({d_1[y], y});
			}
		}
	}
	for (i = 1; i <= n; i ++) d_2[i] = 1e18;
	d_2[fn] = 0;
	pq.push({0, fn});
	
	while ( !pq.empty()) {
		x = pq.top().second;
		s = pq.top().first;
		pq.pop();
		if ( d_2[x] != s) continue;
		for ( pll P : adj[x]) {
			y = P.first;
			c = P.second;
			if( d_2[y] > d_2[x] + c) {
				d_2[y] = d_2[x] + c;
				pq.push({d_2[y], y});
			}
		}
	}
	
	if ( d_1[fn] <= k) {
		r = n * (n - 1)/2;
		cout << r << endl;
		return 0;
	}
	sort ( d_1 + 1, d_1 + n + 1);
	ans = 0;
	for (i = 1; i <= n; i ++) {
		s = k - d_2[i] - cost;
		r = upper_bound(d_1 + 1, d_1 + n + 1, s) - d_1;
		ans += r;
		ans --;
	}
	cout << ans << endl;
	
	
	
	
	
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47