Submission #1304482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304482		witek_cpp	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	1 ms	576 KiB

Main

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

typedef long long ll;

#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define int ll
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

int n;
vvi dist;
vector<vector<pii>> g;

void dijkstra(int s) {
    dist[s].resize(n + 1, -1);
    priority_queue<pii> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int d = -pq.top().st;
        int u = pq.top().nd;
        pq.pop();
        if (dist[s][u] != -1) continue;
        dist[s][u] = d;
        tv(e, g[u]) {
            int v = e.st;
            int w = e.nd;
            if (dist[s][v] == -1) {
                pq.push({-(d + w), v});
            }
        }
    }
}

void solve() {
    int m, s, t, l, k;
    cin >> n >> m >> s >> t >> l >> k;
    g.resize(n + 1);
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].pb({b, c});
        g[b].pb({a, c});
    }
    dist.resize(n + 1);
    dijkstra(s);
    dijkstra(t);
    if (dist[s][t] <= k) {
        cout << (n * (n - 1)) / 2 << "\n";
        return;
    }
    vi a;
    f(i, 1, n + 1) a.pb(dist[s][i]);
    sort(all(a));
    vi b;
    f(i, 1, n + 1) b.pb(dist[t][i]);
    b.pb(-DUZO);
    sort(all(b));
    int ans = 0;
    int j = sz(b) - 1;
    tv(x, a) {
        while (j >= 0 && x + b[j] + l > k) j--;
        ans += j;
    }
    cout << ans << "\n";
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

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