Submission #1230596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230596		TadijaSebez	Construction Project 2 (JOI24_ho_t2)	C++20	53 / 100	121 ms	23272 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=200050;
vector<pair<int,int>> E[N];

ll dist1[N],dist2[N];

const ll inf=1e18;
void Dijkstra(int s,int n,ll dist[]){
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    dist[s]=0;
    priority_queue<pair<ll,int>> pq;
    pq.push({0,s});
    while(pq.size()){
        int u=pq.top().second;
        ll d=-pq.top().first;
        pq.pop();
        if(d!=dist[u])continue;
        for(auto e:E[u]){
            int v,w;
            tie(v,w)=e;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({-dist[v],v});
            }
        }
    }
}
int main(){
    int n,m;
    scanf("%i %i",&n,&m);
    int s,t,l;
    ll k;
    scanf("%i %i %i %lld",&s,&t,&l,&k);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%i %i %i",&u,&v,&w);
        E[u].pb({v,w});
        E[v].pb({u,w});
    }
    Dijkstra(s,n,dist1);
    Dijkstra(t,n,dist2);
    if(dist1[t]<=k){
        printf("%lld\n",(ll)n*(n-1)/2);
    }else{
        vector<ll> all(dist1+1,dist1+1+n);
        sort(all.begin(),all.end());
        ll ans=0;
        for(int i=1;i<=n;i++){
            int lo=upper_bound(all.begin(),all.end(),k-dist2[i]-l)-all.begin();
            ans+=lo;
        }
        printf("%i\n",ans);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:18: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   58 |         printf("%i\n",ans);
      |                 ~^    ~~~
      |                  |    |
      |                  int  long long int
      |                 %lli
Main.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%i %i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%i %i %i %lld",&s,&t,&l,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%i %i %i",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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