Submission #1179590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179590		Szymon_Pilipczuk	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	506 ms	53460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
long long inf = 1e18;
long long dis[2][200000];
vector<vector<vector<long long>>> gr;
priority_queue<vector<long long>> pq;
void dk(long long c,long long p,long long t)
{
    for(int i = 0;i<gr[p].size();i++)
    {
        if(dis[t][gr[p][i][0]] > c + gr[p][i][1])
        {
            dis[t][gr[p][i][0]] = c + gr[p][i][1];
            pq.push({(c + gr[p][i][1])*-1,gr[p][i][0],t});
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,m;
    cin>>n>>m;
    gr.resize(n);
    for(int i = 0;i<n;i++)
    {
        dis[0][i] = inf;
        dis[1][i] = inf;
    }
    long long s,t,xx;
    long long k;
    cin>>s>>t>>xx>>k;
    s--;t--;
    for(int i = 0;i<m;i++)
    {
        long long a,b,d;
        cin>>a>>b>>d;
        a--;b--;
        gr[a].push_back({b,d});
        gr[b].push_back({a,d});
    }
    dis[0][s] = 0;
    dis[1][t] = 0;
    pq.push({0,s,0});
    pq.push({0,t,1});
    while(!pq.empty())
    {
        long long a = pq.top()[0]*-1;
        long long b = pq.top()[1];
        long long c = pq.top()[2];
        pq.pop();
        if(dis[c][b] >= a)
        {
            dk(a,b,c);
        }
    }
    if(dis[0][t] <= k)
    {
        cout<<((long long)n*(n-1))/2<<"\n";
        return 0;
    }
    vector<long long> ct(n);
    for(int i = 0;i<n;i++)
    {
        ct[i] = dis[1][i];
        //cout<<dis[1][i]<<" "<<i<<" "<<ct[i]<<"\n";
    }
    sort(ct.begin(),ct.end());
    reverse(ct.begin(),ct.end());
    vector<long long> cs(n);
    for(int i = 0;i<n;i++)
    {
        cs[i]  =dis[0][i];
    }
    sort(cs.begin(),cs.end());
    long long ans = 0;
    long long j = 0;
    for(int i = 0;i<n;i++)
    {
        while(j != n && ct[j]+cs[i]+xx>k)
        {
            j++;
        }
        //cout<<ct[j]<<" "<<cs[i]<<" "<<xx<<" "<<k<<" "<<j<<" "<<n <<"\n";
        ans+=n-j;
    }
    cout<<ans<<"\n";
}

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