oj.uz

Submission #1095693

# Submission time Handle Problem Language Result Execution time Memory
1095693 2024-10-03T01:47:43 Z zaza Construction Project 2 (JOI24_ho_t2) C++14
0 / 100
 4 ms 8284 KB 
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> g[200005];

long long d[2][200005];

void dij(int i, int s) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
	q.emplace(0, s);
	d[i][s] = 0;
	while (q.size()) {
		int u = q.top().second;
		long long dl = q.top().first;
		q.pop();
		if (dl > d[i][u]) {
			continue;
		}
		for (pair<int, int> p: g[u]) {
			int v = p.first, w = p.second;
			if (d[i][v] > d[i][u] + w) {
				d[i][v] = d[i][u] + w;
				q.emplace(d[i][v], v);
			}
		}
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, s, t, l;
	long long k;
	
	cin >> n >> m >> s >> t >> l >> k;
		
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}

	memset(d, 0x3f3f3f3f, sizeof d);
	
	dij(0, s);
	dij(1, t);
	
	vector<long long> v;
	
	for (int i = 1; i <= n; ++i) {
		v.emplace_back(d[1][i]);
	}
	
	sort(v.begin(), v.end());
	
	long long ans = 0;
	
	for (int i = 1; i <= n; ++i) {
		int j = upper_bound(v.begin(), v.end(), k - l - d[0][i]) - v.begin();
		if (d[1][i] <= k - l - d[0][i]) {
			j--;
		}
		ans += j;
	}
	
	cout << ans << '\n';
	
}
/*
18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645
*/

Compilation message

Main.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main() {
      | ^~~~

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8232 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Incorrect 4 ms 8284 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8264 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8204 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 3 ms 8280 KB Output is correct
9 Correct 3 ms 8280 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Incorrect 3 ms 8156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8264 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8204 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 3 ms 8280 KB Output is correct
9 Correct 3 ms 8280 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Incorrect 3 ms 8156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8232 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Incorrect 4 ms 8284 KB Output isn't correct
7 Halted 0 ms 0 KB -