Submission #1262498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262498		maithedung	Construction Project 2 (JOI24_ho_t2)	C++20	8 / 100	287 ms	50248 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define exit return 0
#define cap pair<int,int>
#define fi first
#define se second
#define pb push_back
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define fill(f,x) memset(f,x,sizeof(f))
#define lcm(a,b) (a/__gcd(a,b)*b)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define iii pair<cap,int>
#define low_bit(x) (x&(-x))
int A[1000005];
int B[1000005];
int n;
int s,t,k,l;
vector<cap> ke[1000005];
int m;
iii C[1000005];
cap A2[1000005];
cap B2[1000005];
int fw[1000005];
int cd[1000005];
void update(int pos, int val)
{
    for(int i=pos;i<=n;i+=low_bit(i)) fw[i]+=val;
}

int get(int pos)
{
    int sum=0;
    for(int i=pos;i>0;i-=low_bit(i)) sum+=fw[i];
    return sum;
}

int query(int l, int r)
{
    return get(r)-get(l-1);
}
void dijk(int s, int visited[])
{
    priority_queue<cap,vector<cap>,greater<cap>> q;
    FOR(i,1,n) visited[i]=1e18;
    q.push({0,s});
    visited[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        int cost=q.top().first;
        q.pop();
        if(cost>visited[u]) continue;
        for(auto it: ke[u])
        {
            int v=it.first;
            int cost2=it.second;
            if(visited[v]>visited[u]+cost2)
            {
                visited[v]=visited[u]+cost2;
                q.push({visited[v],v});
            }
        }
    }
}

bool cmp(iii a, iii b)
{
    return a.first.second<b.first.second;
}
signed main()
{
    fast;
    cin>>n>>m;
    cin>>s>>t>>l>>k;
    FOR(i,1,m)
    {
        int x,y,w;
        cin>>x>>y>>w;
        ke[x].push_back({y,w});
        ke[y].push_back({x,w});
    }
    dijk(s,A);
    dijk(t,B);
    int dem=0;
    if(A[t]<=k)
    {
        cout<<n*(n-1)/2;
        return 0;
    }
    FOR(i,1,n)
    {
        C[i].first.first=A[i];
        C[i].first.second=B[i];
        C[i].second=i;
        A2[i].first=A[i];
        A2[i].second=i;
        B2[i].first=B[i];
        B2[i].second=i;
    }
    sort(C+1,C+1+n,cmp);
    sort(A2+1,A2+1+n,greater<cap>());
    sort(B2+1,B2+1+n);
    FOR(i,1,n)
    {
        cd[C[i].second]=i;
    }
    int j=0;
//    FOR(i,1,n)
//    {
//        FOR(j,i+1,n)
//        {
//            if(min(C[i].first.first+C[j].first.second+l,C[j].first.first+C[i].first.second+l)<=k)
//            {
//                cout<<i<<" "<<j<<endl;
//            }
//        }
//    }
//    FOR(i,1,n) cout<<C[i].first.first<<" ";
//    cout<<endl;
//    FOR(i,1,n) cout<<C[i].first.second<<" ";
  //  cout<<dem<<endl;
    FOR(i,1,n)
    {
        int pos=A2[i].second;
        int val=A2[i].first;
        while(j<n && B2[j+1].first+val<=k-l)
        {
            j+=1;
            update(cd[B2[j].second],1);
        }
        int pos_new=cd[pos];
        val=C[pos_new].first.first;
        int l=1;
        int r=n;
        int ans=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(C[mid].first.second+val<=k-l)
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        int tmp=query(1,n);
        if(ans!=-1)
        {
            tmp+=ans-query(1,ans);
        }
        dem+=tmp;
    }
    cout<<dem;
    exit;
}
/*
░▒▓███████▓▒░░▒▓█▓▒░░▒▓█▓▒░▒▓███████▓▒░ ░▒▓██████▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒▒▓███▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓███████▓▒░ ░▒▓██████▓▒░░▒▓█▓▒░░▒▓█▓▒░░▒▓██████▓▒░


*/

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