Submission #1270356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270356		bhnm	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	206 ms	22188 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
const ll maxn = 2e5 + 5;
const ll inf = 1e17;
ll a[maxn];
ll n,m,s,t,l,k,u,v,w;
bool sub23 = false;
vector<pll>g[maxn];
ll dist1[maxn];
ll distn[maxn];
priority_queue<pll,vector<pll>,greater<pll>>pe;
void dijk1()
{
    for(ll i = 1;i<=n;++i)
    {
        dist1[i] = inf;
    }
    dist1[s] = 0;
    pe.push({0,s});
    while(!pe.empty())
    {
        ll u = pe.top().second;
        ll cur = pe.top().first;
        pe.pop();
        if(dist1[u] < cur)
        {
            continue;
        }
        for(pll v : g[u])
        {
            if(dist1[v.first] > dist1[u] + v.second)
            {
                dist1[v.first] = dist1[u] + v.second;
                pe.push({dist1[v.first],v.first});
            }
        }
    }
}
void dijkn()
{
    for(ll i = 1;i<=n;++i)
    {
        distn[i] = inf;
    }
    distn[t] = 0;
    pe.push({0,t});
    while(!pe.empty())
    {
        ll u = pe.top().second;
        ll cur = pe.top().first;
        pe.pop();
        if(distn[u] < cur)
        {
            continue;
        }
        for(pll v : g[u])
        {
            if(distn[v.first] > distn[u] + v.second)
            {
                distn[v.first] = distn[u] + v.second;
                pe.push({distn[v.first],v.first});
            }
        }
    }
}
void solve()
{
    cin>>n>>m>>s>>t>>l>>k;
    for(ll i = 1;i<=m;++i)
    {
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dijk1();
    dijkn();
    if(n <= 3000)
    {
        sub23 = true;
    }
}
void sub_23()
{
    if(dist1[t] <= k)
    {
        cout<<n*(n-1)/2;
        return;
    }
    ll ans = 0;
    for(ll i = 1;i<n;++i)
    {
        for(ll j = i + 1;j<=n;++j)
        {
            if(dist1[i] + distn[j] + l <= k || distn[i] + dist1[j] + l <= k)
            {
                ans++;
            }
        }
    }
    cout<<ans<<'\n';
}
void sub_14()
{
    if(dist1[t] <= k)
    {
        cout<<n*(n-1)/2;
        return;
    }
    ll ans = 0;
    for(ll i = 1;i<=n;++i)
    {
        if(dist1[i] + distn[i] <= k)
        {
            ans--;
        }
    }
    sort(dist1+1,dist1+n+1);
    sort(distn+1,distn+n+1);
    ll j = n;
    for(ll i = 1;i<=n;++i)
    {
        while(j >= 1 && dist1[i] + distn[j] + l > k)
        {
            j--;
        }
        ans+=j;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("BHNM.INP","r",stdin);
    //freopen("BHNM.OUT","w",stdout);
    ll t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
        if(sub23)
        {
            sub_23();
        }
        else
        {
            sub_14();
        }
    }
    return 0;
}

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