oj.uz

Submission #517630

# Submission time Handle Problem Language Result Execution time Memory
517630 2022-01-23T06:32:46 Z pavement Relay Marathon (NOI20_relaymarathon) C++17
5 / 100
 286 ms 38820 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M, K, ans = 1e16, dist[100005], ddist[100005], st[100005];
bool yes[100005];
iii ed[100005];
vector<ii> adj[100005];
priority_queue<iii, vector<iii>, greater<iii> > pq2;
priority_queue<ii, vector<ii>, greater<ii> > pq;

pair<int, ii> shortest_pair() {
	int fp = 1e16;
	ii fpp;
	for (int i = 1; i <= N; i++) {
		if (yes[i]) {
			dist[i] = 0;
			st[i] = i;
			pq2.emplace(0, i, i);
		} else {
			dist[i] = 1e16;
			st[i] = -1;
		}
	}
	while (!pq2.empty()) {
		auto [d, u, stt] = pq2.top();
		pq2.pop();
		if (d != dist[u]) continue;
		for (auto v : adj[u])
			if (dist[v.first] > d + v.second) {
				dist[v.first] = d + v.second;
				st[v.first] = stt;
				pq2.emplace(dist[v.first], v.first, stt);
			}
	}
	for (int i = 1, u, v, w; i <= M; i++) {
		tie(u, v, w) = ed[i];
		if (st[u] != -1 && st[u] != st[v] && dist[u] + dist[v] + w < fp) {
			fp = dist[u] + dist[v] + w;
			fpp = mp(st[u], st[v]);
		}
	}
	return mp(fp, fpp);
}

void dijk(int s) {
	for (int i = 1; i <= N; i++)
		if (i == s) ddist[i] = 0;
		else ddist[i] = 1e16;
	pq.emplace(0, s);
	while (!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if (d != ddist[u]) continue;
		for (auto v : adj[u])
			if (ddist[v.first] > d + v.second) {
				ddist[v.first] = d + v.second;
				pq.emplace(ddist[v.first], v.first);
			}
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 1, u, v, w; i <= M; i++) {
		cin >> u >> v >> w;
		adj[u].eb(v, w);
		adj[v].eb(u, w);
		ed[i] = mt(u, v, w);
	}
	for (int i = 1, x; i <= K; i++) {
		cin >> x;
		yes[x] = 1;
	}
	auto f = shortest_pair();
	yes[f.second.first] = yes[f.second.second] = 0;
	auto s = shortest_pair();
	ans = min(ans, f.first + s.first);
	yes[f.second.first] = yes[f.second.second] = 1;
	dijk(f.second.first);
	for (int i = 1; i <= N; i++)
		if (yes[i] && i != f.second.first && i != f.second.second) s = min(s, mp(ddist[i], mp(f.second.first, i)));
	dijk(f.second.second);
	for (int i = 1; i <= N; i++)
		if (yes[i] && i != f.second.first && i != f.second.second) s = min(s, mp(ddist[i], mp(f.second.second, i)));
	if (f.second.first != s.second.first && f.second.first != s.second.second && f.second.second != s.second.first && f.second.second != s.second.second) ans = min(ans, f.first + s.first);
	else {
		int fff, sss, common;
		yes[s.second.first] = yes[s.second.second] = 0;
		auto ff = shortest_pair();
		ans = min(ans, ff.first + s.first);
		yes[s.second.first] = yes[s.second.second] = 1;
		for (int x : {f.second.first, f.second.second})
			if (x == s.second.first || x == s.second.second) common = x;
		for (int x : {f.second.first, f.second.second})
			if (x != common) fff = x;
		for (int x : {s.second.first, s.second.second})
			if (x != common) sss = x;
		yes[fff] = yes[sss] = 0;
		auto ffff = shortest_pair();
		dijk(fff);
		ans = min(ans, ffff.first + ddist[sss]);
		yes[fff] = yes[sss] = 1;
	}
	cout << ans << '\n';
}

Compilation message

RelayMarathon.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main() {
      | ^~~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:128:12: warning: 'fff' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |   yes[fff] = yes[sss] = 1;
      |   ~~~~~~~~~^~~~~~~~~~~~~~
RelayMarathon.cpp:127:40: warning: 'sss' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |   ans = min(ans, ffff.first + ddist[sss]);
      |                               ~~~~~~~~~^
RelayMarathon.cpp:121:4: warning: 'common' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |    if (x != common) fff = x;
      |    ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2764 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2764 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2764 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 2 ms 2636 KB Output is correct
24 Correct 2 ms 2636 KB Output is correct
25 Correct 2 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2764 KB Output is correct
29 Correct 2 ms 2764 KB Output is correct
30 Correct 2 ms 2764 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2764 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2764 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2764 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 2 ms 2636 KB Output is correct
24 Correct 2 ms 2636 KB Output is correct
25 Correct 2 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2764 KB Output is correct
29 Correct 2 ms 2764 KB Output is correct
30 Correct 2 ms 2764 KB Output is correct
31 Correct 2 ms 2648 KB Output is correct
32 Correct 3 ms 2768 KB Output is correct
33 Correct 3 ms 2768 KB Output is correct
34 Correct 2 ms 2648 KB Output is correct
35 Correct 1 ms 2644 KB Output is correct
36 Correct 5 ms 3032 KB Output is correct
37 Correct 4 ms 3156 KB Output is correct
38 Correct 2 ms 2776 KB Output is correct
39 Correct 31 ms 9280 KB Output is correct
40 Correct 7 ms 4172 KB Output is correct
41 Correct 2 ms 2764 KB Output is correct
42 Correct 8 ms 4228 KB Output is correct
43 Correct 3 ms 2904 KB Output is correct
44 Correct 2 ms 2764 KB Output is correct
45 Correct 2 ms 2636 KB Output is correct
46 Runtime error 35 ms 19536 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10632 KB Output is correct
2 Correct 7 ms 5708 KB Output is correct
3 Correct 286 ms 22056 KB Output is correct
4 Correct 272 ms 25244 KB Output is correct
5 Runtime error 156 ms 38820 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2764 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2764 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2764 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 2 ms 2636 KB Output is correct
24 Correct 2 ms 2636 KB Output is correct
25 Correct 2 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2764 KB Output is correct
29 Correct 2 ms 2764 KB Output is correct
30 Correct 2 ms 2764 KB Output is correct
31 Correct 2 ms 2648 KB Output is correct
32 Correct 3 ms 2768 KB Output is correct
33 Correct 3 ms 2768 KB Output is correct
34 Correct 2 ms 2648 KB Output is correct
35 Correct 1 ms 2644 KB Output is correct
36 Correct 5 ms 3032 KB Output is correct
37 Correct 4 ms 3156 KB Output is correct
38 Correct 2 ms 2776 KB Output is correct
39 Correct 31 ms 9280 KB Output is correct
40 Correct 7 ms 4172 KB Output is correct
41 Correct 2 ms 2764 KB Output is correct
42 Correct 8 ms 4228 KB Output is correct
43 Correct 3 ms 2904 KB Output is correct
44 Correct 2 ms 2764 KB Output is correct
45 Correct 2 ms 2636 KB Output is correct
46 Runtime error 35 ms 19536 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -