Submission #1200380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200380		Ablabla	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	209 ms	22184 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const ll INF = 1e18 + 7;

int main() {
	ll n, m;
	cin >> n >> m;

	ll s, t, l, k;
	cin >> s >> t >> l >> k;
	s--; t--;

	vector<vector<pii>> csucsok(n, vector<pii>());
	for(ll i = 0; i < m; i++){
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;

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

	vector<ll> tTol(n, INF);
	vector<bool> bejart(n);
	priority_queue<pii/*, vector<pii>, greater<pii>*/> bejar;
	bejar.push({0, t});
	tTol[t] = 0;

	while(!bejar.empty()){
		ll akt = bejar.top().second;
		bejar.pop();

		if(bejart[akt]) continue;
		bejart[akt] = 1;

		for(pii x : csucsok[akt]){
			if(bejart[x.first]) continue;

			if(tTol[x.first] > tTol[akt] + x.second){
				tTol[x.first] = tTol[akt] + x.second;
				bejar.push({-tTol[x.first], x.first});
			}
		}
	}

	vector<ll> sTol(n, INF);
	bejart.assign(n, 0);
	bejar.push({0, s});
	sTol[s] = 0;

	while(!bejar.empty()){
		ll akt = bejar.top().second;
		bejar.pop();

		if(bejart[akt]) continue;
		bejart[akt] = 1;

		for(pii x : csucsok[akt]){
			if(bejart[x.first]) continue;
			
			if(sTol[x.first] > sTol[akt] + x.second){
				sTol[x.first] = sTol[akt] + x.second;
				bejar.push({-sTol[x.first], x.first});
			}
		}
	}

	if(sTol[t] <= k){
		cout << n*(n - 1) / 2 << "\n";
		return 0;
	}

	sort(tTol.begin(), tTol.end(), greater<ll>());
	sort(sTol.begin(), sTol.end());

	ll ind = 0;
	ll ans = 0;

	for(ll i = 0; i < n; i++){
		while(ind < tTol.size() && sTol[i] + tTol[ind] + l > k){
			ind++;
		}

		ans += n - ind;
	}

	cout << ans << "\n";
}

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