Submission #1145556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145556		ezzzay	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	215 ms	28624 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int a[N];
vector<pair<int,int>>v[N];
int dst[2][N];
void djk(int x, int s){
	priority_queue<pair<int,int>>q;
	for(int i=0;i<N;i++){
		dst[x][i]=1e17;
	}
	dst[x][s]=0;
	q.push({0,s});
	while(!q.empty()){
		int w= -q.top().ff;
		int a=q.top().ss;
		q.pop();
		if(w>dst[x][a])continue;
		for(auto p:v[a]){
			int b=p.ff;
			int c=p.ss;
			if(dst[x][b] > dst[x][a]+c){
				dst[x][b]=dst[x][a]+c;
				q.push({-dst[x][b],b});
			}
		}
	}
}
signed main(){
	int n,m,s,t,l,k;
	cin>>n>>m>>s>>t>>l>>k;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		v[a].pb({b,c});
		v[b].pb({a,c});
	}
	djk(0,s);
	djk(1,t);
	if(dst[0][t]<=k){
		cout<<(n-1)*n/2;
		return 0;
	}
	int ans=0;
	vector<int>vc;
	
	
	
	for(int i=1;i<=n;i++){
		vc.pb(dst[1][i]);
	}
	sort(vc.begin(),vc.end());
	for(int i=1;i<=n;i++){
		auto it= upper_bound(vc.begin(),vc.end(), k-l-dst[0][i]);
		int idx= it-vc.begin();
		if(dst[0][i]+dst[1][i]+l<=k)ans--;
		ans+=idx;
	}
	cout<<ans;
}

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