제출 #1148481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148481		Cookie197	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	715 ms	97628 KiB

Main

// Cookie197 
// i am absolute trash
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include <cassert>
#include<random>
using namespace std;
#define i_am_trashQ_Q ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pii pair<ll,ll>
#define mp make_pair
#define mod 998244353
//#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

ll n,m,s,t;
ll L,K,ds[200005],dt[200005];
vector<pii> adj[200005];
vector<pii> P,Q;
set<ll> all;
map<ll,ll> tosmall;
int tobig[600005];

bool sort_ds(pii a,pii b){
    return a.first < b.first;
}
bool sort_dt(pii a,pii b){
    return a.second < b.second;
}

ll bit[600005];
void update(int id,int x){
    for (int i=id;i<=600002;i+=(i&-i)){
        bit[i] += x;
    }
}
int sum(int k){
    if (k <= 0) return 0;
    int ans = 0;
    for (int i=k;i>0;i-=(i&-i)){
        ans += bit[i];
    }
    return ans;
}
signed main(){
    i_am_trashQ_Q;
    cin>>n>>m;
    cin>>s>>t>>L>>K;
    for (int i=1;i<=m;i++){
        ll a,b,c; cin>>a>>b>>c;
        adj[a].push_back(mp(b,c));
        adj[b].push_back(mp(a,c));
    }
    for (int i=1;i<=n;i++) ds[i] = dt[i] = 1e18;

    priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push(mp(0,s));
    while(!pq.empty()){
        int now=pq.top().second;
        ll dis=pq.top().first;
        pq.pop();
        if(ds[now] != 1e18)continue;
        ds[now] = dis;
        for (pii p:adj[now]){
            if (ds[p.first] != 1e18) continue;
            pq.push(mp(dis+p.second,p.first));
        }
    }

    pq.push(mp(0,t));
    while(!pq.empty()){
        int now=pq.top().second;
        ll dis=pq.top().first;
        pq.pop();
        if(dt[now] != 1e18)continue;
        dt[now] = dis;
        for (pii p:adj[now]){
            if (dt[p.first] != 1e18) continue;
            pq.push(mp(dis+p.second,p.first));
        }
    }
    if (ds[t] <= K) {cout<<n*(n-1)/2<<endl; return 0;}

    //n = 7; K = 24; L = 0;
    //ds[1] = 5; ds[2] = 7; ds[3] = 10; ds[4] = 13; ds[5] = 14; ds[6] = 16; ds[7] = 19;
    //dt[1] = 10; dt[2] = 8; dt[3] = 16; dt[4] = 9; dt[5] = 8; dt[6] = 15; dt[7] = 9;
    
    for (int i=1;i<=n;i++) P.push_back(mp(ds[i], dt[i])), Q.push_back(mp(ds[i], dt[i])), all.insert(ds[i]), all.insert(dt[i]), all.insert(K-L+1-dt[i]);
    sort(P.begin(), P.end(), sort_ds); sort(Q.begin(), Q.end(), sort_dt);
    //for (int i=0;i<n;i++) cout<<Q[i].first<<" "<<Q[i].second<<endl;
    int cnt = 0;
    for (ll u:all) cnt++, tosmall[u] = cnt, tobig[cnt] = u;
    //for (int i=1;i<=cnt;i++) out2(tobig, i);

    ll bad_pairs = 0;
    int r = n;
    for (int i=0;i<n;i++){
        while(r >= 1){
            if (P[i].first + Q[r-1].second >= K-L+1){
                r--;
                update(tosmall[Q[r].first], 1);
                //out(Q[r].first);
            }else break;
        }
        ll x = 0;
        if (P[i].second >= K-L+1) x = sum(600002);
        else x = sum(600002) - sum(tosmall[K-L+1-P[i].second] - 1);
        //out(x);
        bad_pairs += x;
    }
    for (int i=1;i<=n;i++) if (ds[i] + dt[i] >= K-L+1) bad_pairs--;

    cout<<n*(n-1)/2 - bad_pairs/2<<endl;
}

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