Submission #1268635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268635		ducksaysquack	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	254 ms	23820 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
	int n, m, s, t, l, k; cin >> n >> m >> s >> t >> l >> k; s--, t--;
	vector<vector<pair<int,int>>> adj(n); 
	for(int i=0;i<m;i++) {
		int x, y, z; cin >> x >> y >> z; x--, y--;
		adj[x].push_back({y,z}), adj[y].push_back({x,z});
	}
	vector<int> ds(n,1e18), dt(n,1e18); vector<bool> ps(n), pt(n);
	ds[s] = 0, dt[t] = 0; priority_queue<pair<int,int>> q; q.push({0,s});
	while(!q.empty()) {
		int a = q.top().second; q.pop();
		if(ps[a]) continue; ps[a] = true;
		for(auto u:adj[a]) {
			int b = u.first, w = u.second;
			if(ds[a]+w < ds[b]) {ds[b] = ds[a]+w; q.push({-ds[b],b});}
		}
	}
	q.push({0,t}); while(!q.empty()) {
		int a = q.top().second; q.pop();
		if(pt[a]) continue; pt[a] = true;
		for(auto u:adj[a]) {
			int b = u.first, w = u.second;
			if(dt[a]+w < dt[b]) {dt[b] = dt[a]+w; q.push({-dt[b],b});}
		}
	}
	if(ds[t] <= k) {cout << n*(n-1)/2; return 0;}
	sort(begin(ds),end(ds)), sort(begin(dt),end(dt));
	int ans = 0, y = n-1;
	for(int i=0;i<n;i++) {while(y >= 0 && dt[y]+ds[i] > k-l) y--; ans += y+1;}
	cout << ans;
}

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