Submission #1164126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164126		WH8	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	185 ms	28056 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;
	//~ queue<int> q;
	//~ q.push(x);
	//~ while(!q.empty()){
		//~ int c=q.front();
		//~ q.pop();
		//~ cout<<c<<endl;
		//~ for(auto it:al[c]){
			//~ if(dist[it.f].f>dist[c].f+1){
				//~ dist[it.f].f=dist[c].f+1;
				//~ q.push(it.f);
			//~ }
		//~ }
	//~ }
	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;
	int ans=0, cur=0, ptr=0;
	bool tcov[n+1]; fill(tcov, tcov+n+1, false);
	bool scov[n+1]; fill(scov, scov+n+1, false);

	for(int i=n-1;i>=0;i--){
		while(ptr<n and distt[ptr].f + dists[i].f + l <= k){
			tcov[distt[ptr].s]=1;
			if(!scov[distt[ptr].s])cur++;
			ptr++;
		}
		scov[dists[i].s]=1;
		if(tcov[dists[i].s])cur++;
		//~ printf("i %lld, ptr %lld, cur %lld\n", i, ptr, cur);
		ans+=max(0ll, ptr-cur);
	}
	cout<<ans;
}

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