제출 #1369627

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

Main

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

const long long INF = (long long)4e18;

struct Fenwick{
    int n;
    vector<long long> bit;

    Fenwick(int n = 0){
        this->n = n;
        bit.assign(n + 1, 0);
    }

    void add(int idx, long long val){
        idx++;
        while(idx <= n){
            bit[idx] += val;
            idx += idx & -idx;
        }
    }

    long long sum(int idx){
        if(idx < 0) return 0;
        long long res = 0;
        idx++;
        while(idx > 0){
            res += bit[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

vector<long long> dijkstra(int src, vector<vector<pair<int, long long> > > &adj){
    int n = adj.size();
    vector<long long> dist(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;

    dist[src] = 0;
    pq.push({0, src});

    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();

        if(d != dist[u]) continue;

        for(auto [v, w] : adj[u]){
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main(){
    int N, M;
    cin >> N >> M;

    int S, T;
    long long L, K;
    cin >> S >> T >> L >> K;
    S--;
    T--;

    vector<vector<pair<int, long long> > > adj(N);

    for(int i = 0; i < M; i++){
        int A, B;
        long long C;
        cin >> A >> B >> C;
        A--;
        B--;

        adj[A].push_back({B, C});
        adj[B].push_back({A, C});
    }

    vector<long long> dS = dijkstra(S, adj);
    vector<long long> dT = dijkstra(T, adj);

    long long totalPairs = 1LL * N * (N - 1) / 2;

    if(dS[T] <= K){
        cout << totalPairs << '\n';
        return 0;
    }

    long long B = K - L;

    if(B < 0){
        cout << 0 << '\n';
        return 0;
    }
    vector<long long> sortedDT = dT;
    sort(sortedDT.begin(), sortedDT.end());

    long long directed = 0;

    for(int i = 0; i < N; i++){
        long long need = B - dS[i];

        long long cnt = upper_bound(sortedDT.begin(), sortedDT.end(), need) - sortedDT.begin();

        if(dS[i] + dT[i] <= B){
            cnt--;
        }

        directed += cnt;
    }
    vector<long long> vals = dT;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    vector<int> points(N);
    iota(points.begin(), points.end(), 0);

    sort(points.begin(), points.end(), [&](int x, int y){
        return dS[x] < dS[y];
    });

    vector<int> queries(N);
    iota(queries.begin(), queries.end(), 0);

    sort(queries.begin(), queries.end(), [&](int x, int y){
        return B - dT[x] < B - dT[y];
    });

    Fenwick fw(vals.size());

    int ptr = 0;
    long long bothDirected = 0;

    for(int i : queries){
        long long maxDS = B - dT[i];

        while(ptr < N && dS[points[ptr]] <= maxDS){
            int node = points[ptr];
            int pos = lower_bound(vals.begin(), vals.end(), dT[node]) - vals.begin();
            fw.add(pos, 1);
            ptr++;
        }

        long long maxDT = B - dS[i];
        int pos = upper_bound(vals.begin(), vals.end(), maxDT) - vals.begin() - 1;

        long long cnt = fw.sum(pos);

        if(dS[i] + dT[i] <= B){
            cnt--;
        }

        bothDirected += cnt;
    }

    long long answer = directed - bothDirected / 2;

    cout << answer << '\n';
    return 0;
}

• 서브태스크 1: 8 / 8
• 서브태스크 2: 16 / 16
• 서브태스크 3: 29 / 29
• 서브태스크 4: 47 / 47