Submission #1170745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170745		akqxolotl	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	154 ms	24644 KiB

Main

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

#define int long long
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define fi first
#define se second
typedef pair<int,int> pii;
#define pb push_back

bool svis[200005];
int sdis[200005];
bool tvis[200005];
int tdis[200005];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m;cin>>n>>m;
	int s,t,l,k;cin>>s>>t>>l>>k;
	vector<pair<int,int>> adj[n+1];
	
	for(int i=0;i<m;i++){
		int x,y,w;cin>>x>>y>>w;
		adj[x].pb({y,w});
		adj[y].pb({x,w});
	}
	
	for(int i=0;i<=n;i++){
		tdis[i]=LLONG_MAX;
		sdis[i]=LLONG_MAX;
	}
	
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	
	pq.push({0,s});
	
	while(!pq.empty()){
		int cd=pq.top().fi;
		int cn=pq.top().se;
		pq.pop();
		if(svis[cn])continue;
		svis[cn]=1;
		sdis[cn]=cd;
		
		for(pii p:adj[cn]){
			if(svis[p.fi])continue;
			pq.push({p.se+cd,p.fi});
		}
	}
	
	pq.push({0,t});
	
	while(!pq.empty()){
		int cd=pq.top().fi;
		int cn=pq.top().se;
		pq.pop();
		if(tvis[cn])continue;
		tvis[cn]=1;
		tdis[cn]=cd;
		
		for(pii p:adj[cn]){
			if(tvis[p.fi])continue;
			pq.push({p.se+cd,p.fi});
		}
	}
	
	if(tdis[s]<=k){
		cout<<(n-1)*n/2<<'\n';
		return 0;
	}
	
	vector<int> ss;
	
	for(int i=1;i<=n;i++){
		//debug(tdis[i])
		ss.pb(tdis[i]);
	}
	
	sort(ss.begin(),ss.end());
	//for(auto i:ss)debug(i)
	//for(int i=0;i<n;i++)debug(tdis[i])
	
	int ans=0;
	
	for(int i=1;i<=n;i++){
		
		int temp=(upper_bound(ss.begin(),ss.end(),(k-l-sdis[i]))-ss.begin());
		if(sdis[i]==LLONG_MAX)continue;
		//debug(sdis[i])
		//debug(temp)
		ans+=temp;
	}
	cout<<ans<<'\n';
}
	

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