Submission #1164118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164118		WH8	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	2092 ms	27876 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)

#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
vector<vector<pll>> al(200005);
int n,m,s,t,l,k;
int fw[200005];
int pitr[200005];
vector<pll> dists(200005,{LLONG_MAX, LLONG_MAX}), distt(200005, {LLONG_MAX, LLONG_MAX});
void upd(int x, int v){
	if(x==0)assert(false);
	while(x<=n){
		fw[x]+=v;
		x+=(x&-x);
	}
}
int qry(int x){
	int ret=0;
	while(x>0){
		ret+=fw[x];
		x-=(x&-x);
	}
	return ret;
}

void dijkstra(int x, vector<pll> & dist){
	for(int i=1; i<=n;i++)dist[i].f=1e16, dist[i].s=i;
	dist[x].f=0;
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	pq.push({0, x});
	while(!pq.empty()){
		auto [d,c]=pq.top();
		//~ printf("at %lld \n", c);
		pq.pop();
		if(dist[c].f<d)continue;
		for(auto [u, v]:al[c]){
			if(dist[u].f<d+v)continue;
			dist[u].f=d+v;
			pq.push({dist[u].f,u});
		}
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m>>s>>t>>l>>k;
	
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		al[a].pb({b,c});
		al[b].pb({a,c});
	}
	dijkstra(s, dists);
	dijkstra(t, distt);
	if(dists[t].f <= k){
		cout<<(n*(n-1))/2;
		return 0;
	}
	sort(dists.begin(), dists.end());
	sort(distt.begin(),distt.end());
	for(int i=0;i<n;i++){
		pitr[distt[i].s]=i+1;
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<dists[i].f<<" "<<dists[i].s<<" |";
	//~ }cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<distt[i].f<<" "<<distt[i].s<<" |";
	//~ }cout<<endl;
	//~ for(int i=1;i<=n;i++){
		//~ cout<<pitr[i]<<" ";
	//~ }cout<<endl;
	for(int i=1;i<=n;i++){
		upd(i, 1);
	}
	int ans=0;
	for(int i=0;i<n;i++){
		//~ cout<<k-l-dists[i].f<<endl;
		int av=upper_bound(distt.begin(),distt.end(),make_pair(k-l-dists[i].f, LLONG_MAX)) - distt.begin();
		int non=qry(av);
		ans+=non;
		//~ printf("i %lld, av %lld, non %lld, pitr[dists[i].s] %lld\n",i,av,non,pitr[dists[i].s]);
		upd(pitr[dists[i].s], -1);
	}
	cout<<ans;
}

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