oj.uz

Submission #1111261

# Submission time Handle Problem Language Result Execution time Memory
1111261 2024-11-11T22:51:03 Z StefanSebez Construction Project 2 (JOI24_ho_t2) C++14
45 / 100
 103 ms 26548 KB 
#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;
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 6 ms 5456 KB Output is correct
6 Correct 5 ms 5456 KB Output is correct
7 Correct 80 ms 26548 KB Output is correct
8 Correct 103 ms 26360 KB Output is correct
9 Incorrect 86 ms 22288 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5116 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 5 ms 5200 KB Output is correct
5 Correct 4 ms 5200 KB Output is correct
6 Correct 4 ms 5200 KB Output is correct
7 Correct 5 ms 5200 KB Output is correct
8 Correct 5 ms 5200 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 4 ms 5200 KB Output is correct
11 Correct 4 ms 5200 KB Output is correct
12 Correct 5 ms 4944 KB Output is correct
13 Correct 4 ms 4952 KB Output is correct
14 Correct 4 ms 4944 KB Output is correct
15 Correct 4 ms 4944 KB Output is correct
16 Correct 4 ms 4944 KB Output is correct
17 Correct 4 ms 5200 KB Output is correct
18 Correct 4 ms 5200 KB Output is correct
19 Correct 6 ms 5148 KB Output is correct
20 Correct 4 ms 5016 KB Output is correct
21 Correct 4 ms 5200 KB Output is correct
22 Correct 4 ms 5200 KB Output is correct
23 Correct 4 ms 5200 KB Output is correct
24 Correct 4 ms 5200 KB Output is correct
25 Correct 4 ms 5148 KB Output is correct
26 Correct 5 ms 5200 KB Output is correct
27 Correct 4 ms 5200 KB Output is correct
28 Correct 4 ms 5200 KB Output is correct
29 Correct 4 ms 5200 KB Output is correct
30 Correct 5 ms 5200 KB Output is correct
31 Correct 4 ms 4944 KB Output is correct
32 Correct 4 ms 4944 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5116 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 5 ms 5200 KB Output is correct
5 Correct 4 ms 5200 KB Output is correct
6 Correct 4 ms 5200 KB Output is correct
7 Correct 5 ms 5200 KB Output is correct
8 Correct 5 ms 5200 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 4 ms 5200 KB Output is correct
11 Correct 4 ms 5200 KB Output is correct
12 Correct 5 ms 4944 KB Output is correct
13 Correct 4 ms 4952 KB Output is correct
14 Correct 4 ms 4944 KB Output is correct
15 Correct 4 ms 4944 KB Output is correct
16 Correct 4 ms 4944 KB Output is correct
17 Correct 4 ms 5200 KB Output is correct
18 Correct 4 ms 5200 KB Output is correct
19 Correct 6 ms 5148 KB Output is correct
20 Correct 4 ms 5016 KB Output is correct
21 Correct 4 ms 5200 KB Output is correct
22 Correct 4 ms 5200 KB Output is correct
23 Correct 4 ms 5200 KB Output is correct
24 Correct 4 ms 5200 KB Output is correct
25 Correct 4 ms 5148 KB Output is correct
26 Correct 5 ms 5200 KB Output is correct
27 Correct 4 ms 5200 KB Output is correct
28 Correct 4 ms 5200 KB Output is correct
29 Correct 4 ms 5200 KB Output is correct
30 Correct 5 ms 5200 KB Output is correct
31 Correct 4 ms 4944 KB Output is correct
32 Correct 4 ms 4944 KB Output is correct
33 Correct 5 ms 5456 KB Output is correct
34 Correct 5 ms 5456 KB Output is correct
35 Correct 5 ms 5456 KB Output is correct
36 Correct 6 ms 5456 KB Output is correct
37 Correct 6 ms 5456 KB Output is correct
38 Correct 4 ms 5456 KB Output is correct
39 Correct 7 ms 5456 KB Output is correct
40 Correct 5 ms 5456 KB Output is correct
41 Correct 5 ms 5200 KB Output is correct
42 Correct 5 ms 5420 KB Output is correct
43 Correct 6 ms 5456 KB Output is correct
44 Correct 6 ms 5456 KB Output is correct
45 Correct 6 ms 5456 KB Output is correct
46 Correct 7 ms 5456 KB Output is correct
47 Correct 6 ms 5456 KB Output is correct
48 Correct 6 ms 5456 KB Output is correct
49 Correct 5 ms 5200 KB Output is correct
50 Correct 5 ms 5456 KB Output is correct
51 Correct 7 ms 5456 KB Output is correct
52 Correct 6 ms 5456 KB Output is correct
53 Correct 6 ms 5456 KB Output is correct
54 Correct 6 ms 5456 KB Output is correct
55 Correct 7 ms 5632 KB Output is correct
56 Correct 5 ms 5456 KB Output is correct
57 Correct 6 ms 5456 KB Output is correct
58 Correct 6 ms 5456 KB Output is correct

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 4 ms 5200 KB Output is correct
5 Correct 6 ms 5456 KB Output is correct
6 Correct 5 ms 5456 KB Output is correct
7 Correct 80 ms 26548 KB Output is correct
8 Correct 103 ms 26360 KB Output is correct
9 Incorrect 86 ms 22288 KB Output isn't correct
10 Halted 0 ms 0 KB -