Submission #1262170

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

Main

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int n, m, s, t, l;
ll k;
vector<ii> g[N];
ll d[2][N], a[N], b[N];

void Dijkstra(int sr, ll d[]) {
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0, sr});
    FOR(i, 1, n) d[i] = INF;
    d[sr] = 0;
    while(!pq.empty()) {
        ll cost = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(cost != d[u]) continue;
        for(auto H : g[u]) {
            int v = H.fi;
            int w = H.se;
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

ll ans;

vector<ll> val;
int cnt;

struct Bit {
    int bit[2 * N];

    void reset() {
        FOR(i, 1, cnt) bit[i] = 0;
    }

    void up(int x, int val) {
        for(; x <= cnt; x += x & -x) bit[x] += val;
    }

    int get(int x) {
        int ret = 0;
        for(; x; x -= x & -x) ret += bit[x];
        return ret;
    }

    int getrange(int l, int r) {
        return (l > 1 ? get(r) - get(l - 1) : get(r));
    }
};
Bit bit;

int get_idx(int x) {
    return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}

void process(ll a[], ll b[]) {
    FOR(i, 1, n) {
        val.pb(a[i]);
        val.pb(-b[i]);
    }
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    cnt = val.size();
    FOR(i, 1, n) {
        ans += bit.getrange(get_idx(a[i]), cnt);
        bit.up(get_idx(-b[i]), 1);
    }
    bit.reset();
    val.clear();
}

void KhoiLe() {
    Dijkstra(s, d[0]);
    Dijkstra(t, d[1]);

    if(d[0][t] <= k) {
        cout << (1LL * n * (n - 1) / 2) << '\n';
        return;
    }

    /// x < y
    /// d1[x] + dn[y] + l <= k <=> dn[y] + l - k <= -d1[x]
    /// dn[x] + d1[y] + l <= k <=> d1[y] + k - k <= -dn[x]

    FOR(i, 1, n) {
        a[i] = d[1][i] + l - k;
//        cout << a[i] << ' ' << -d[0][i] << '\n';
        b[i] = d[0][i] + l - k;
    }
    process(a, d[0]);
    process(b, d[1]);

    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;
    while(test--) {
        cin >> n >> m >> s >> t >> l >> k;
        FOR(i, 1, m) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].pb({v, w});
            g[v].pb({u, w});
        }
        KhoiLe();
    }
}

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