Submission #1161012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161012		hijackedsoul	Construction Project 2 (JOI24_ho_t2)	C++20	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = LLONG_MAX / 4;

struct Edge {
    int to, w;
};

int N, M, S, T, L, K;
vector<vector<Edge>> adj;

vector<int> dijkstra(int source) {
    vector<int> dist(N+1, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dist[source] = 0;
    pq.push({0, source});
    while (!pq.empty()){
        auto [d, cur] = pq.top(); pq.pop();
        if(d != dist[cur]) continue;
        for(auto &e : adj[cur]){
            int nd = d + e.w;
            if(nd < dist[e.to]){
                dist[e.to] = nd;
                pq.push({nd, e.to});
            }
        }
    }
    return dist;
}

// A Fenwick tree (Binary Indexed Tree) for point updates and range sum queries.
struct Fenw {
    int n;
    vector<int> fenw;
    Fenw(int n) : n(n), fenw(n+1, 0) { }
    void update(int i, int delta) {
        for(++i; i <= n; i += i & -i)
            fenw[i] += delta;
    }
    int query(int i) {
        int s = 0;
        for(++i; i > 0; i -= i & -i)
            s += fenw[i];
        return s;
    }
    int rangeQuery(int l, int r) {
        if(l > r) return 0;
        return query(r) - (l == 0 ? 0 : query(l-1));
    }
};

// For offline queries on the BIT.
struct Query {
    int T_threshold; // We want to count indices j with d_T[j] <= T_threshold.
    int L;           // The query is over j in the sorted array with index in [L, n-1]
    int idx;         // Which node i this query corresponds to (for book‐keeping)
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M >> S >> T >> L >> K;
    adj.resize(N+1);
    for (int i = 0; i < M; i++){
        int a, b, c; 
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    // Compute distances from S and T.
    vector<int> ds = dijkstra(S);
    vector<int> dt = dijkstra(T);
    
    // Build array of (d_S, d_T) for nodes 1..N.
    vector<pair<int,int>> arr;
    arr.reserve(N);
    for (int i = 1; i <= N; i++){
        arr.push_back({ds[i], dt[i]});
    }
    // Sort by d_S.
    sort(arr.begin(), arr.end(), [](auto &a, auto &b) {
        return a.first < b.first;
    });
    int n = arr.size(); // = N
    
    // For each node (as candidate u, with index i in arr), we count the number of nodes v (with v > u)
    // such that:
    //    either: d_S[v] <= (K - L - d_T[u])   (this guarantees d_S[v] + d_T[u] <= K - L)
    // or, if d_S[v] > (K - L - d_T[u]), then we require d_T[v] <= (K - L - d_S[u])
    //
    // For each i we:
    //   (1) Let j0 = first index j > i with arr[j].first > (K - L - d_T[u]).
    //       Then for all j in [i+1, j0) condition (2) holds automatically.
    //   (2) For j in [j0, n), we need arr[j].second <= (K - L - arr[i].first).
    // We will count (1) directly and (2) via offline BIT queries.
    
    vector<int> term1(n, 0);  // term1[i] = count for j in [i+1, j0)
    vector<Query> queries;    // queries for nodes in [j0, n)
    
    for (int i = 0; i < n; i++){
        if(i == n-1) continue; // no j available for the last element
        // Bound for condition (2): we want d_S[v] <= (K - L - d_T[u]).
        int bound_ds = K - L - arr[i].second;
        // Find first index j (with j > i) such that arr[j].first > bound_ds.
        int j0 = int(upper_bound(arr.begin() + i + 1, arr.end(), bound_ds, 
            [](int val, const pair<int,int> &p){ return val < p.first; }) - arr.begin());
        // For j in [i+1, j0), condition (2) holds automatically.
        int cnt1 = max(0LL, j0 - (i+1));
        term1[i] = cnt1;
        // For indices j in [j0, n), we require d_T[v] <= (K - L - d_S[u]).
        int L_bound = max(i+1, j0);  // we only consider j > i
        if(L_bound < n) {
            int T_threshold = K - L - arr[i].first; // condition: d_T[v] <= this threshold.
            queries.push_back({T_threshold, L_bound, i});
        }
    }
    
    // Now we answer the queries offline.
    // We'll build a BIT over indices 0..n-1 (the array positions in arr).
    // To answer a query "in indices [L_bound, n-1], count how many j have d_T[j] <= T_threshold",
    // we first sort indices j by arr[j].second.
    vector<pair<int,int>> dtArr;
    for (int j = 0; j < n; j++){
        dtArr.push_back({arr[j].second, j});
    }
    sort(dtArr.begin(), dtArr.end()); // sorted by d_T value (ascending)
    
    // Sort queries by T_threshold (ascending)
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b){
        return a.T_threshold < b.T_threshold;
    });
    
    Fenw fenw(n);
    long long total_term2 = 0;
    int pointer = 0;
    // Process each query in increasing order of threshold.
    for (auto &q : queries) {
        while(pointer < n && dtArr[pointer].first <= q.T_threshold){
            int pos = dtArr[pointer].second;
            fenw.update(pos, 1); // mark that index pos qualifies (its d_T is small enough)
            pointer++;
        }
        int cnt = fenw.rangeQuery(q.L, n-1);
        total_term2 += cnt;
    }
    
    // Sum over all i the counts from (1) and (2).
    long long total_term1 = 0;
    for (int i = 0; i < n; i++){
        total_term1 += term1[i];
    }
    long long ans = total_term1 + total_term2;
    cout << ans << "\n";
    
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:3:13: error: expected primary-expression before 'long'
    3 | #define int long long
      |             ^~~~
Main.cpp:108:18: note: in expansion of macro 'int'
  108 |         int j0 = int(upper_bound(arr.begin() + i + 1, arr.end(), bound_ds,
      |                  ^~~