제출 #1111261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111261		StefanSebez	Construction Project 2 (JOI24_ho_t2)	C++14	45 / 100	103 ms	26548 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,M=4e5+50;
const ll inf=1e18;
vector<pair<ll,ll>>E[N];
ll dist[N][2];bool was[N];
priority_queue<pair<ll,ll>>kju;
int bit[M+50];
void Update(int i,int x){for(i++;i<=M;i+=i&-i)bit[i]+=x;}
int Get(int i){int x=0;for(i++;i>=1;i-=i&-i)x+=bit[i];return x;}
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.top().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.top().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});
			}
		}
    }
    ll res=0;
    if(dist[T][0]<=K){
		res=(ll)(n*(n-1))/2;
		printf("%lld\n",res);
		return 0;
    }
    //for(int i=1;i<=n;i++) printf("%i: %lld %lld\n",i,dist[i][0],dist[i][1]);
    vector<int>ind;for(int i=1;i<=n;i++) ind.pb(i);
    sort(ind.begin(),ind.end(),[&](int i,int j){return dist[i][1]<dist[j][1];});
    vector<ll>Vals;
    for(int i=1;i<=n;i++){
		Vals.pb(dist[i][1]+L);
		Vals.pb(K-dist[i][0]);
    }
    sort(Vals.begin(),Vals.end());
    int mm=unique(Vals.begin(),Vals.end())-Vals.begin();
    Vals.resize(mm);
    //for(auto i:Vals) printf("%lld ",i);printf("\n");
    for(auto i:ind){
		//printf("%i\n",i);
		/*ll l=1,r=n,lb=0;
		while(l<=r){
			ll mid=l+r>>1;
			if(B[mid]<=x){lb=mid;l=mid+1;}
			else r=mid-1;
		}*/
		res+=Get(upper_bound(Vals.begin(),Vals.end(),K-dist[i][0])-Vals.begin());
		Update(upper_bound(Vals.begin(),Vals.end(),dist[i][1]+L)-Vals.begin(),1);
		//for(int j=1;j<=7;j++) printf("%i ",bit[j]);printf("\n");
		//if(dist[i][1]<=x) res--;
    }
    printf("%lld\n",res);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     int n,m;scanf("%i%i",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~
Main.cpp:18:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     int S,T;ll L,K;scanf("%i%i%lld%lld",&S,&T,&L,&K);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   int u,v;ll w;scanf("%i%i%lld",&u,&v,&w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~

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