Submission #1158452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158452		dubabuba	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	219 ms	24808 KiB

Main

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

typedef long long int i64;
#define int long long
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const i64 inf = 1e18 + 10;
const int mxn = 2e5 + 10;

vector<i64> st, en;
vector<pii> adj[mxn];
int n, m, s, e, len;
i64 lim;

void djkstra(int st, vector<i64> &dis) {
	dis.resize(n + 1, inf);
	priority_queue<pii> pq;
	pq.push(MP(0, st));

	while(pq.size()) {
		int d = -pq.top().ff;
		int u = pq.top().ss;
		pq.pop();

		if(dis[u] < inf) continue;
		dis[u] = d;

		for(pii p : adj[u]) {
			int v = p.ff;
			int c = p.ss + d;
			if(dis[v] == inf)
				pq.push(MP(-c, v));
		}
	}
}

int32_t main() {
	cin >> n >> m;
	cin >> s >> e >> len >> lim;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(MP(b, c));
		adj[b].push_back(MP(a, c));
	}

	djkstra(s, st);
	djkstra(e, en);

	if(st[e] <= lim) {
		i64 ans = 1LL * n * (n - 1) / 2;
		cout << ans << endl;
		return 0;
	}

	st[0] = en[0] = -1;
	sort(st.begin(), st.end());
	sort(en.begin(), en.end());

	i64 ans = 0LL;
	for(int i = 1; i <= n; i++) {
		i64 sus = lim - len - st[i];
		if(sus < 0) continue;
		i64 add = upper_bound(en.begin(), en.end(), sus) - en.begin() - 1;
		ans += add;
	}

	cout << ans << endl;
	return 0;
}

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