Submission #1179571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179571		pythontest	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	233 ms	35024 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;
constexpr int N=2e5+7;
vector<pair<long long,int>> graf[N];
long long distfroms[N];
long long distfromt[N];
constexpr int MJ=20;
long long tree[1<<MJ];
void rundikstra(int start, long long *tab){
    priority_queue<pair<long long, int>> kolejka;
    kolejka.push({0,start});
    while(!kolejka.empty()){
        auto top = kolejka.top();
        top.first=-top.first;
        kolejka.pop();
        if(tab[top.second]<=top.first) continue;
        tab[top.second]=top.first;
        for(auto x:graf[top.second]){
            long long nd = top.first+x.first;
            if(tab[x.second]>nd)
                kolejka.push({-nd,x.second});
        }
    }
}
void update(int n, long long v){
    n+=1<<(MJ-1);
    tree[n]+=v;
    n>>=1;
    while(n){
        tree[n]=tree[2*n]+tree[2*n+1];
        n>>=1;
    }
}
long long read(int a, int b){
    a+=1<<(MJ-1);
    b+=1<<(MJ-1);
    long long res = tree[a];
    if(a!=b) res+=tree[b];
    while((a>>1)!=(b>>1)){
        if(a%2==0) res+=tree[a+1];
        if(b%2==1) res+=tree[b-1];
        a>>=1;
        b>>=1;
    }
    return res;
}
unordered_map<long long, int> mapka;
int main() {
    long long n,m;
    scanf("%lld %lld",&n,&m);
    int s,t;
    long long c,k;
    scanf("%d %d %lld %lld",&s,&t,&c,&k);
    for(int i=0;i<m;i++){
        int a,b;
        long long c;
        scanf("%d %d %lld",&a,&b,&c);
        graf[a].push_back({c,b});
        graf[b].push_back({c,a});
    }
    for(int i=0;i<=n;i++) distfroms[i]=distfromt[i]=1e18;
    rundikstra(s,distfroms);
    rundikstra(t,distfromt);
    if(k>=distfroms[t]){
        printf("%lld",(n*(n-1))/2);
        exit(0);
    }
    vector<pair<long long, int>> distvec;
    distvec.reserve(n);
    for(int i=1;i<=n;i++) distvec.push_back({distfroms[i],i});
    sort(distvec.begin(),distvec.end());
    vector<long long> przepisana;
    przepisana.reserve(n);
    for(int i=1;i<=n;i++) przepisana.push_back(distfromt[i]);
    sort(przepisana.begin(),przepisana.end());
    for(int i=0;i<n;i++)  mapka[przepisana[i]]=i+1;
    for(int i=0;i<n;i++) update(mapka[przepisana[i]],1);
    long long wyn=0;
    for(int i=0;i<n;i++){
        update(mapka[distfromt[distvec[i].second]],-1);
        long long req = k-distvec[i].first-c+1;
        auto p = lower_bound(przepisana.begin(), przepisana.end(), req);
        int index = p-przepisana.begin();
        if(index!=0){
            wyn+=read(1,index);
        }
    }
    printf("%lld",wyn);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d %d %lld %lld",&s,&t,&c,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d %d %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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