Submission #991211

#	Time	Username	Problem	Language	Result	Execution time	Memory
991211		model_code	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	863 ms	57120 KiB

Main

// 別解

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

using P = pair<long long, int>;

struct edge{
    int to;
    long long cost;
};

template< typename S, S (*op)(S, S), S (*e)() >
struct segmenttree{
    private:
    int _n;
    std::vector<S> node;

    public:
    segmenttree() = default;
      
    segmenttree(int n){
        _n = 1;
        while(_n < n){
            _n *= 2;
        }
        node.resize(2 * _n, e());
    }
    segmenttree(std::vector<S> &v){
        int n = v.size();
        _n = 1;
        while(_n < n){
            _n *= 2;
        }
        node.resize(2 * _n, e());
        for(int i = 0; i < n; i++){
            set(i, v[i]);
        }
    }

    // [i] <- val
    void set(int i, S val){
        i += _n;
        node[i] = val;
        while(i > 1){
            i >>= 1;
            node[i] = op(node[2 * i], node[2 * i + 1]);
        }
    }

    // [i] <- op([i],val)
    void update(int i, S val){
        i += _n;
        node[i] = op(node[i], val);
        while(i > 1){
            i >>= 1;
            node[i] = op(node[2 * i], node[2 * i + 1]);
        }
    }

    S get(int i){
        i += _n;
        return node[i];
    }

    S prod(int l,int r){
        S pdl=e(), pdr=e();
        l += _n;
        r += _n;

        while(l < r){
            if(l & 1){
              pdl = op(pdl, node[l++]);
            }
            if(r & 1){
                pdr = op(node[--r], pdr);
            }
            l >>= 1;
            r >>= 1;
        }

        return op(pdl, pdr);
    };
};

int op(int a, int b){
    return a + b;
}

int e(){
    return 0;
}

constexpr long long inf = 1e18;

int main(){
    int n, m;
    cin >> n >> m;
    
    int s, t;
    long long l, k;
    cin >> s >> t >> l >> k;
    s--;
    t--;

    vector<vector<edge>> g(n);
    for(int i = 0; i < m; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--;
        b--;

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    priority_queue<P, vector<P>, greater<P>> que;
    vector<long long> dist_from_s(n, inf), dist_from_t(n, inf);

    dist_from_s[s] = 0;
    que.push({0, s});
    while(!que.empty()){
        auto [dist, now] = que.top();
        que.pop();

        if(dist_from_s[now] < dist){
            continue;
        }

        for(auto [nxt, c]: g[now]){
            if(dist_from_s[nxt] > dist + c){
                dist_from_s[nxt] = dist + c;
                que.push({dist + c, nxt});
            }
        }
    }

    dist_from_t[t] = 0;
    que.push({0, t});
    while(!que.empty()){
        auto [dist, now] = que.top();
        que.pop();

        if(dist_from_t[now] < dist){
            continue;
        }

        for(auto [nxt, c]: g[now]){
            if(dist_from_t[nxt] > dist + c){
                dist_from_t[nxt] = dist + c;
                que.push({dist + c, nxt});
            }
        }
    }

    if(dist_from_s[t] <= k){
        cout << (long long)(n) * (n - 1) / 2 << endl;
        return 0;
    }

    vector<long long> val = dist_from_s;
    for(int i = 0; i < n; i++){
        val.emplace_back(dist_from_t[i]);
    }
    sort(val.begin(), val.end());

    map<long long, int> index;
    for(int i = 0; i < 2 * n; i++){
        index[val[i]] = i;
    }

    segmenttree<int, op, e> seg1(2 * n), seg2(2 * n);
    long long ans = 0;

    for(int i = 0; i < n; i++){
        long long ok = k - l - dist_from_s[i];
        ans += seg2.prod(0, lower_bound(val.begin(), val.end(), ok + 1) - val.begin());
        ok = k - l - dist_from_t[i];
        ans += seg1.prod(0, lower_bound(val.begin(), val.end(), ok + 1) - val.begin());
        
        seg1.update(index[dist_from_s[i]], 1);
        seg2.update(index[dist_from_t[i]], 1);
    }

    cout << ans << endl;
}

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