Submission #1162686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162686		emptypringlescan	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	138 ms	24452 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    int s,t;
    long long l,k;
    cin >> s >> t >> l >> k;
    vector<pair<int,long long> > adj[n+1];
    for(int i=0; i<m; i++){
		int a,b;
		long long c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > pq;
	long long dist[2][n+1];
	memset(dist,-1,sizeof(dist));
	pq.push({0,s});
	while(!pq.empty()){
		long long a=pq.top().first;
		int b=pq.top().second;
		pq.pop();
		if(dist[0][b]!=-1) continue;
		dist[0][b]=a;
		for(auto i:adj[b]){
			if(dist[0][i.first]!=-1) continue;
			pq.push({a+i.second,i.first});
		}
	}
	pq.push({0,t});
	while(!pq.empty()){
		long long a=pq.top().first;
		int b=pq.top().second;
		pq.pop();
		if(dist[1][b]!=-1) continue;
		dist[1][b]=a;
		for(auto i:adj[b]){
			if(dist[1][i.first]!=-1) continue;
			pq.push({a+i.second,i.first});
		}
	}
	for(int i=1; i<=n; i++){
		if(dist[0][i]==-1) dist[0][i]=1e16;
		if(dist[1][i]==-1) dist[1][i]=1e16;
	}
	if(dist[0][t]<=k){
		cout << (long long)n*(n-1)/2ll;
		return 0;
	}
	vector<long long> yey;
	for(int i=1; i<=n; i++) yey.push_back(dist[0][i]);
	sort(yey.begin(),yey.end());
	long long ans=0;
	for(int i=1; i<=n; i++){
		ans+=upper_bound(yey.begin(),yey.end(),k-l-dist[1][i])-yey.begin();
	}
	cout << ans;
}

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