Submission #1111256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111256		StefanSebez	Construction Project 2 (JOI24_ho_t2)	C++14	0 / 100	6 ms	5200 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50;
const ll inf=1e18;
vector<pair<int,ll>>E[N];
ll dist[N][2];bool was[N];
queue<pair<ll,int>>kju;
int main(){
    int n,m;scanf("%i%i",&n,&m);
    int S,T;ll L,K;scanf("%i%i%lld%lld",&S,&T,&L,&K);
    for(int i=1;i<=m;i++){
		int u,v;ll w;scanf("%i%i%lld",&u,&v,&w);
		E[u].pb({v,w}),E[v].pb({u,w});
    }
    for(int i=1;i<=n;i++) dist[i][0]=dist[i][1]=inf;
    dist[S][0]=0;
    kju.push({0,S});
    while(kju.size()){
		int u=kju.front().se;kju.pop();
		if(was[u]) continue;
		was[u]=true;
		for(auto i:E[u]){
			if(!was[i.fi]&&dist[i.fi][0]>dist[u][0]+i.se){
				dist[i.fi][0]=dist[u][0]+i.se;
				kju.push({-dist[i.fi][0],i.fi});
			}
		}
    }
    for(int i=1;i<=n;i++) was[i]=false;
    dist[T][1]=0;
    kju.push({0,T});
	while(kju.size()){
		int u=kju.front().se;kju.pop();
		if(was[u]) continue;
		was[u]=true;
		for(auto i:E[u]){
			if(!was[i.fi]&&dist[i.fi][1]>dist[u][1]+i.se){
				dist[i.fi][1]=dist[u][1]+i.se;
				kju.push({-dist[i.fi][1],i.fi});
			}
		}
    }
    //for(int i=1;i<=n;i++) printf("%i: %lld %lld\n",i,dist[i][0],dist[i][1]);
    ll A[n+10],B[n+10];
    for(int i=1;i<=n;i++) A[i]=dist[i][0],B[i]=dist[i][1];
    sort(A+1,A+n+1);sort(B+1,B+n+1);
    ll res=0;
    for(int i=1;i<=n;i++){
		ll x=K-L-dist[i][0];
		int l=1,r=n,lb=0;
		while(l<=r){
			int mid=l+r>>1;
			if(B[mid]<=x){lb=mid;l=mid+1;}
			else r=mid-1;
		}
		res+=lb;
		if(dist[i][1]<=x) res--;
    }
    printf("%lld\n",res);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |    int mid=l+r>>1;
      |            ~^~
Main.cpp:14:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     int n,m;scanf("%i%i",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~
Main.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     int S,T;ll L,K;scanf("%i%i%lld%lld",&S,&T,&L,&K);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   int u,v;ll w;scanf("%i%i%lld",&u,&v,&w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~

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