Submission #1272310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272310		goulthen	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	150 ms	26644 KiB

Main

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

#define int long long
#define ll long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back

const int MAXN = 2e5+10;
const int INF = 1e18 + 5;
const int MOD = 1e9+7;
vector<pii> g[MAXN];
int dist[MAXN][2],n;
bool vis[MAXN][2];

void dijkstra(int u, int k) {
	rep(i,1,n) dist[i][k] = INF;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0,u});
	dist[u][k] = 0;

	while (!pq.empty()) {
		auto [d, cur] = pq.top();pq.pop();
		if(vis[cur][k]) continue;
		vis[cur][k] = 1;

		for(auto &[v,w] : g[cur]) {
			if (dist[v][k] <= d+w) continue;
			dist[v][k] = d+w;
			pq.push({d+w,v});
		}
	}
}

void solve() {
	int m,s,t,l,k;
	cin >> n >> m >> s >> t >> l >> k;
	rep(i,1,m) {
		int u,v,c;cin >> u >> v >> c;
		g[u].pb({v,c});
		g[v].pb({u,c});
	}

	dijkstra(s,0);
	dijkstra(t,1);

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

	vector<pii> val;
	vector<int> bs;
	rep(i,1,n) val.pb({dist[i][0], dist[i][1]});
	sort(val.begin(),val.end());

	int cnt = 0;
	for(auto &[du,dv] : val) {
		cnt += upper_bound(bs.begin(),bs.end(),k-l-dv) - bs.begin();

		//cout << du << ' ' << dv << ' ' << upper_bound(bs.begin(),bs.end(),k-l-dv) - bs.begin() << '\n';

		bs.pb(du);
	}
	cout << cnt << '\n';
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int tt = 1;
	//cin >> tt;

	while (tt--) solve();
	return 0;
}

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