Submission #1057342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057342		beaconmc	Construction Project 2 (JOI24_ho_t2)	C++14	100 / 100	215 ms	38832 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;

const ll maxn = 200005;
const ll INF = 10000000000000000;
vector<array<ll, 2>> edges[maxn];
ll dists[maxn];
ll distt[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	FOR(i,0,maxn) dists[i] = INF, distt[i] = INF;

	ll n,m;
	cin >> n >> m;
	ll s, t, l, k;
	cin >> s >> t >> l >> k;
	FOR(i,0,m){
		ll a,b,c;
		cin >> a >> b >> c;

		edges[a].push_back({b,c});
		edges[b].push_back({a,c});
	}

	priority_queue<vector<ll>> pq;
	dists[s] = 0;
	pq.push({0, s});

	while (pq.size()){
		vector<ll> node = pq.top(); pq.pop();

		node[0] = -node[0];
		if (dists[node[1]] != node[0]) continue;

		for (auto&i : edges[node[1]]){
			if (dists[i[0]] > dists[node[1]] + i[1]){
				dists[i[0]] = dists[node[1]] + i[1];
				pq.push({-dists[i[0]] , i[0]});
			}
		}
	}
	distt[t] = 0;
	pq.push({0, t});

	while (pq.size()){
		vector<ll> node = pq.top(); pq.pop();

		node[0] = -node[0];
		if (distt[node[1]] != node[0]) continue;

		for (auto&i : edges[node[1]]){
			if (distt[i[0]] > distt[node[1]] + i[1]){
				distt[i[0]] = distt[node[1]] + i[1];
				pq.push({-distt[i[0]] , i[0]});
			}
		}
	}

	if (dists[t] <= k) cout << n * (n-1) / 2;
	else{
		ll ans = 0;
		vector<ll> S, T;
		FOR(i,1,n+1) S.push_back(dists[i]), T.push_back(distt[i]);
		sort(S.begin(), S.end());
		sort(T.begin(), T.end());


		FOR(i,0,n){
			ll req = k - (S[i]+l);
			ll sus = upper_bound(T.begin(), T.end(), req) - T.begin();
			ans += sus;
		}

		cout << ans << endl;

	}




}

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