Submission #1187389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187389		prideliqueee	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	386 ms	48928 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct st
{
    int u,w;
    bool operator < (const st&o) const
    {
        return w>o.w;
    }
};
map<pair<int,int>,int> mp;
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    int ss,tt,l,k;
    cin>>ss>>tt>>l>>k;
    vector<pair<int,int>> ad[n+1];
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        ad[u].push_back({v,w});
        ad[v].push_back({u,w});
        if(u>v)
        swap(u,v);
        mp[{u,v}]=w;
    }
    pair<int,int> dists[n+1],distt[n+1];
    for(int i=1;i<=n;i++)
    {
        dists[i]={i,LLONG_MAX};
        distt[i]={i,LLONG_MAX};
    }
    dists[ss].s=0;
    distt[tt].s=0;
    priority_queue<st> q;
    q.push({ss,0});
    while(!q.empty())
    {
        auto p=q.top();
        q.pop();
        int u=p.u,w=p.w;
        if(dists[u].s<w)
        continue;
        for(auto x:ad[u])
        {
            if(dists[x.f].s>w+x.s)
            {
                dists[x.f].s=w+x.s;
                q.push({x.f,w+x.s});
            }
        }
    }
    q.push({tt,0});
    while(!q.empty())
    {
        auto p=q.top();
        q.pop();
        int u=p.u,w=p.w;
        if(distt[u].s<w)
        continue;
        for(auto x:ad[u])
        {
            if(distt[x.f].s>w+x.s)
            {
                distt[x.f].s=w+x.s;
                q.push({x.f,w+x.s});
            }
        }
    }
    if(dists[tt].s<=k)
    {
        cout<<(n*(n-1))/2;
        return 0;
    }
    sort(dists+1,dists+n+1,[](auto &x,auto &y)
    {
        return x.s<y.s;;
    });
    sort(distt+1,distt+n+1,[](auto &x,auto &y)
    {
        return x.s<y.s;;
    });
    int ans=0;
    set<int> sss;
    for(int i=1;i<=n;i++)
    sss.insert(i);
    deque<int> dq;
    int dist[n+1];
    for(int i=1;i<=n;i++)
    {
        dq.push_back(distt[i].f);
        dist[distt[i].f]=distt[i].s;
    }
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty()&&((dists[i].s==LLONG_MAX)||(dist[dq.back()]==LLONG_MAX)||(dists[i].s+l+dist[dq.back()]>k)))
        {
            sss.erase(dq.back());
            dq.pop_back();
        }
        sss.erase(dists[i].f);
        ans+=sss.size();
    }
    
    /*int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int sp=LLONG_MAX;
            int ll=LLONG_MAX;
            if(dists[i].s!=ll&&distt[j].s!=ll)
            {
                sp=dists[i].s+distt[j].s+l;
                //if(mp[{i,j}]!=0)
                //sp=min(sp,dists[i].s+distt[j].s+mp[{i,j}]);
            }
            if(distt[i].s!=ll&&dists[j].s!=ll)
            {
                sp=min(sp,distt[i].s+dists[j].s+l);
                //if(mp[{i,j}]!=0)
                //sp=min(sp,distt[i].s+dists[j].s+mp[{i,j}]);
            }
            if(sp<=k)
            ans++;
            else if(dists[tt].s<=k)
            ans++;
        }
    }*/
    cout<<ans;
}

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