Submission #1182756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182756		Dedibeat	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	5 ms	5192 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define F first
#define S second 
#define all(x) (x).begin(), (x).end()

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(const T &v, int lim = 1e9)
{
    for(auto x : v) 
        if(lim-- > 0) cout << x << " ";
    cout << "\n";
}
#define int long long
int N, M, S, T, L, K;
using node = pair<ll, ll>;
vector<node> adj[200005];


struct Node {
    ll val;       // Value of the segment (e.g., sum)
    Node *left;   // Left child
    Node *right;  // Right child aa
    Node() : val(0), left(nullptr), right(nullptr) {}
};
class DynamicSegmentTree {
private:
    Node* root;
    ll l_bound, r_bound;
    void update(Node*& node, ll l, ll r, ll idx, ll value) {
        if (!node) node = new Node();
        if (l == r) {
            node->val += value;
            return;
        }
        ll mid = l + (r - l) / 2;
        if (idx <= mid) {
            update(node->left, l, mid, idx, value);
        } else {
            update(node->right, mid + 1, r, idx, value);
        }
        node->val = getValue(node->left) + getValue(node->right);
    }
    ll query(Node* node, ll l, ll r, ll ql, ll qr) {
        if (!node || ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) {
            return node->val;
        }
        ll mid = l + (r - l) / 2;
        return query(node->left, l, mid, ql, qr) + query(node->right, mid + 1, r, ql, qr);
    }
    ll getValue(Node* node) {
        return node ? node->val : 0;
    }
public:
    DynamicSegmentTree(ll l_bound, ll r_bound) : l_bound(l_bound), r_bound(r_bound), root(nullptr) {}
    void update(ll idx, ll value) {
        update(root, l_bound, r_bound, idx, value);
    }
    ll query(ll ql, ll qr) {
        return query(root, l_bound, r_bound, ql, qr);
    }
};


signed main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M >> S >> T >> L >> K;
    for(int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    auto dij = [&](int start)
    {
        priority_queue<node, vector<node> , greater<node>> q;
        vector<ll> d(N + 5, 1e17);
        d[start] = 0;
        q.emplace(0, start);
        while(!q.empty())
        {
            auto [c, v] = q.top(); q.pop();
            if(c != d[v]) continue;
            for(auto [u, w] : adj[v])
            {
                if(c + w < d[u])
                {
                    d[u] = c + w;
                    q.emplace(c + w, u);
                }
            }
        }
        return d;
    };


    auto ds = dij(S);
    auto dt = dij(T);

  //  print(ds);
  //  print(dt);

    ll cnt = 0;

    vector<int> vert;
    for(int i = 1; i <= N; i++)
        vert.push_back(i);
    
    sort(vert.begin(), vert.end(), [&](int v, int u)
    {
        return ds[v] - dt[v] < ds[u] - dt[u];
    });

    DynamicSegmentTree st(0, 1e18);
    for(int v : vert)
    {
       // cout <<"node "<<  v << " " << dt[v] << " " << ds[v] << endl;
        cnt += st.query(0, K - L - dt[v]);
        st.update(ds[v], 1);
    }

    cout << cnt << "\n";

    
}

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