Submission #1262112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262112		tdkhai	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	602 ms	37384 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ii pair<int,int>
#define llll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define tdk "metro"
#define int long long
using namespace std;
const ll INF =1e18;
const int N=2e5+5;
vector<ii> a[N];
ll d[3][N],k,ans,ft[4*N],ft2[4*N];
int n,m,s,t,L;
vector<ll> vec;
void dijkstra(int id,int beg)
{
    for(int i=1;i<=n;i++) d[id][i]=INF;
    d[id][beg]=0;
    priority_queue<llll,vector<llll>,greater<llll>> pq;
    pq.push({0,beg});
    while(pq.size())
    {
        ll w=pq.top().fi;
        int u=pq.top().se;
        pq.pop();
        if(d[id][u]!=w)
            continue;
        for(int i=0;i<a[u].size();i++)
        {
            int v=a[u][i].fi,c=a[u][i].se;
            if(d[id][v]>d[id][u]+c)
            {
                d[id][v]=d[id][u]+c;
                pq.push({d[id][v],v});
            }
        }
    }
}
void update(int u)
{
    while(u<=vec.size())
    {
        ft[u]++;
        u+=(u&(-u));
    }
}
ll get(int u)
{
    ll ret=0;
    while(u)
    {
        ret+=ft[u];
        u-=(u&(-u));
    }
    return ret;
}
void update2(int u,int val)
{
    while(u)
    {
        ft2[u]+=val;
        u-=(u&(-u));
    }
}
ll get2(int u)
{
    ll ret=0;
    while(u<=vec.size())
    {
        ret+=ft2[u];
        u+=(u&(-u));
    }
    return ret;
}
void solve()
{
    cin >>n >> m >> s >> t >> L >> k;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>> u >> v >> w;
        a[u].pb({v,w});
        a[v].pb({u,w});
    }
    dijkstra(1,s);
    dijkstra(2,t);
    if(d[1][t]<=k)
    {
        cout << (n*(n-1))/2;
        return;
    }
    if(L>k and d[1][t]>k)
    {
        cout <<0;return;
    }
    if(n<=5e3)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                ll mn=d[1][t];//    cout << ans << ":\n";

                if(d[1][i]+d[2][j]+L<=k or d[2][i]+d[1][j]+L<=k)
                {
//                    cout << i << ' ' << j << '\n';
                    ans++;
                }
            }
        }
        cout << ans;
        return;
    }
    for(int t=1;t<=2;t++)
    {
        for(int i=1;i<=n;i++)
        {
//            cnt[t][d[t][i]]++;
            vec.pb(d[t][i]);
            vec.pb(k-d[t][i]-L);
//            cout << t << ' ' << i << ' ' << d[t][i] << '\n';
        }
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=1;i<=n;i++)
    {
        int l=0,r=vec.size()-1,ok=0;
//        cout << k << ' ' << d[2][i] << ' ' <<L << ":::" << k-d[2][i]-L << ' ';
        ll cur=k-d[2][i]-L;
//        cout << d[1][i] << ' ' << d[2][i] << ' ';
        while(l<=r)
        {
            int mid=l+r>>1;
            if(vec[mid]<=cur)
            {
                l=mid+1;
                ok=vec[mid];
            }
            else
            {
                r=mid-1;
            }
        }
        ok=lower_bound(vec.begin(),vec.end(),ok)-vec.begin()+1;
//        cout << i << ' ' << get(ok) << ' ' << ok << ' ' << cur  << '\n';
        ans+=get(ok);
//        cout << ans << '\n';
        cur=lower_bound(vec.begin(),vec.end(),d[1][i])-vec.begin()+1;
//        cout << cur << '\n';
        update(cur);
    }
//    cout << ans << ":\n";
    for(int i=1;i<=vec.size();i++) ft[i]=0;
    for(int i=1;i<=n;i++)
    {
        int ok=lower_bound(vec.begin(),vec.end(),k-d[2][i]-L)-vec.begin()+1;
        update2(ok,1);
    }
    for(int i=1;i<=n;i++)
    {
        int l=0,r=vec.size()-1,ok=0;
//        cout << k << ' ' << d[2][i] << ' ' <<L << ":::" << k-d[2][i]-L << ' ';
        ll cur=k-d[1][i]-L;
//        cout << d[1][i] << ' ' << d[2][i] << ' ';
        while(l<=r)
        {
            int mid=l+r>>1;
            if(vec[mid]<=cur)
            {
                l=mid+1;
                ok=vec[mid];
            }
            else
            {
                r=mid-1;
            }
        }
        ok=lower_bound(vec.begin(),vec.end(),ok)-vec.begin()+1;
//        cout << i << ' ' << get(ok) << ' ' << ok << ' ' << cur  << '\n';
        ans+=get(ok);
//        ok=lower_bound(vec.begin(),vec.end(),k-d[2][i]-L)-vec.begin()+1;
//        update2(ok,-1);
//        ok=lower_bound(vec.begin(),vec.end(),d[1][i])-vec.begin()+1;
//        ans-=get2(ok);
        cur=lower_bound(vec.begin(),vec.end(),d[2][i])-vec.begin()+1;
//        cout << ans <<'\n';
//        cout << cur << '\n';
        update(cur);
    }
    cout << ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen(tdk".inp","r",stdin);
    // freopen(tdk".out","w",stdout);
    int t=1;//cin >> t;
    while(t--)
    {
        solve();
    }
    cerr <<"\n\n\ Time elapsed: " << 1024.0*clock()/CLOCKS_PER_SEC << "mb ans:" << ans <<'\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:205:12: warning: unknown escape sequence: '\040'
  205 |     cerr <<"\n\n\ Time elapsed: " << 1024.0*clock()/CLOCKS_PER_SEC << "mb ans:" << ans <<'\n';
      |            ^~~~~~~~~~~~~~~~~~~~~~

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