Submission #1262196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262196		tuanmwillwinvoi26	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	3 ms	5444 KiB

Main

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

#define el '\n'
#define TASK "metro"
#define int long long

const int INF = (int)4e18;
const int MAXN = 200000 + 5;

int n, m;
int s, t, l, k;
vector<pair<int,int>> adj[MAXN];
int dist_s[MAXN], dist_t[MAXN];

void dijkstra(int src, int dist[]) {
    for (int i = 1; i <= n; ++i) dist[i] = INF;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (d != dist[u]) continue;
        for (auto &e : adj[u]) {
            int v = e.first, w = e.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// Fenwick for counts
struct Fenwick {
    int n;
    vector<int> ft;
    Fenwick(int _n=0){ init(_n); }
    void init(int _n){ n=_n; ft.assign(n+1,0); }
    void add(int i,int v){ for(; i<=n; i += i&-i) ft[i]+=v; }
    int sum(int i){ int r=0; for(; i>0; i -= i&-i) r+=ft[i]; return r; }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (fopen(TASK".inp","r")){
        freopen(TASK".inp","r",stdin);
        freopen(TASK".out","w",stdout);
    }

    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    dijkstra(s, dist_s);
    dijkstra(t, dist_t);

    long long W = k - l;

    // vt: chỉ chứa dist_t[j] hữu hạn
    vector<long long> vt;
    vt.reserve(n);
    for (int j = 1; j <= n; ++j) if (dist_t[j] < INF) vt.push_back(dist_t[j]);
    sort(vt.begin(), vt.end());

    // ordered count (including self if it satisfies) but later we'll remove self
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist_s[i] == INF) continue;
        long long want = W - dist_s[i];
        if (want < 0) continue;
        long long pos = upper_bound(vt.begin(), vt.end(), want) - vt.begin();
        res += pos;
    }

    // self_count: số i thỏa dist_s[i] + dist_t[i] <= W (và cả hai hữu hạn)
    long long self_count = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist_s[i] < INF && dist_t[i] < INF && dist_s[i] + dist_t[i] <= W) ++self_count;
    }

    // Chuẩn bị cho phần đếm "both" (các cặp {i,j} i!=j mà cả hai hướng đều thỏa)
    // Chỉ lấy các nút có cả hai khoảng cách hữu hạn
    vector<pair<long long,int>> nodesByA;
    vector<long long> allB;
    nodesByA.reserve(n);
    allB.reserve(n);
    for (int j = 1; j <= n; ++j){
        if (dist_s[j] < INF && dist_t[j] < INF){
            nodesByA.push_back({dist_s[j], j});
            allB.push_back(dist_t[j]);
        }
    }
    sort(nodesByA.begin(), nodesByA.end()); // theo A tăng

    // queries: chỉ với i có cả hai khoảng cách hữu hạn
    struct Query { long long alpha; long long beta; };
    vector<Query> queries; queries.reserve(n);
    for (int i = 1; i <= n; ++i){
        if (dist_s[i] < INF && dist_t[i] < INF){
            long long alpha = W - dist_t[i]; // A_j <= alpha
            long long beta  = W - dist_s[i]; // B_j <= beta
            queries.push_back({alpha, beta});
        }
    }
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b){
        return a.alpha < b.alpha;
    });

    // compress B's (từ allB)
    vector<long long> uniqB = allB;
    sort(uniqB.begin(), uniqB.end());
    uniqB.erase(unique(uniqB.begin(), uniqB.end()), uniqB.end());
    auto getBRank = [&](long long x)->int{
        int pos = upper_bound(uniqB.begin(), uniqB.end(), x) - uniqB.begin(); // pos in [0..sz]
        return pos;
    };

    Fenwick bit((int)uniqB.size() + 5);

    long long ordered_sum_including_self = 0;
    int p = 0; // pointer trên nodesByA
    for (auto &q : queries){
        long long alpha = q.alpha;
        long long beta  = q.beta;
        // thêm tất cả nodes với A_j <= alpha
        while (p < (int)nodesByA.size() && nodesByA[p].first <= alpha){
            int j = nodesByA[p].second;
            long long Bj = dist_t[j];
            int r = getBRank(Bj);
            if (r > 0) bit.add(r, 1);
            p++;
        }
        if (beta < 0) continue;
        int rBeta = getBRank(beta);
        if (rBeta > 0) ordered_sum_including_self += bit.sum(rBeta);
    }

    // ordered_both_excl_self = ordered_sum_including_self - self_count
    long long ordered_both_excl_self = ordered_sum_including_self - self_count;
    if (ordered_both_excl_self < 0) ordered_both_excl_self = 0;
    long long unordered_both = ordered_both_excl_self / 2;

    // Kết luận: ordered res đã gồm các ordered pairs (i,j) (bao gồm self).
    // Để đếm mỗi unordered {i,j} (i!=j) một lần và bỏ hoàn toàn i==j:
    long long answer_no_self = res - unordered_both - self_count;
    if (answer_no_self < 0) answer_no_self = 0;

    cout << answer_no_self << el;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen(TASK".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(TASK".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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