Submission #1127067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127067		czauderna	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	198 ms	24904 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
const int N = 2e5+3;
const ll INF = 2e18;
vector<pair<ll, int>> grf[N];
ll odl[2][N];
void dij(int v, int t){
	odl[t][v]=0;
	priority_queue<pair<ll, int>> Q;
	Q.push({0, v});
	while(!Q.empty()){
		int cur =  Q.top().nd;
		ll wg = -Q.top().st;
		Q.pop();
		if(odl[t][cur]<wg) continue;
		for(auto w:grf[cur]){
			if(wg+w.nd<odl[t][w.st]){
				odl[t][w.st]=wg+w.nd;
				Q.push({-odl[t][w.st], w.st});
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n, m, l, k;
	int s, t;
	cin >> n >> m;
	cin >> s >> t >> l >> k;
	for(int i=0; i<m; i++){
		int a, b; ll c;
		cin >> a >> b >> c;
		grf[a].pb({b, c});
		grf[b].pb({a, c});
	}
	for(int i=1; i<=n; i++) odl[0][i]=odl[1][i]=INF;
	dij(s, 0);
	dij(t, 1);
	ll out=0;
	if(odl[0][t]<=k){
		out=n*(n-1); out/=2;
		cout << out << '\n';
		return 0;
	}
	sort(odl[0]+1, odl[0]+1+n);
	sort(odl[1]+1, odl[1]+1+n, greater<ll>());
	int ptr=1;
	for(int i=1; i<=n; i++){
		while(ptr<=n && odl[0][i]+odl[1][ptr]>k-l) ptr++;
		out+=n-ptr+1;
	}
	cout << out << '\n';
	return 0;
}

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