oj.uz

Submission #379948

# Submission time Handle Problem Language Result Execution time Memory
379948 2021-03-19T19:13:59 Z nikatamliani Relay Marathon (NOI20_relaymarathon) C++14
100 / 100
 2098 ms 135576 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {
	return a + (unsigned long long)rng() % (b - a + 1);
}
const int oo = 1e9+10;
int calc(vector<int> &a, vector<int> &b, vector<vector<pair<int, int>>> &edges) {
	priority_queue<pair<int,int>> q;
	for(int x : a) {
		q.push({0, x});
	}
	vector<bool> fix(n), seen(n);
	for(int x : b) {
		fix[x] = 1;
	}
	while(!q.empty()) {
		pair<int,int> p = q.top(); q.pop();
		if(fix[p.second]) return -p.first;
		if(seen[p.second]) continue;
		seen[p.second] = 1;
		for(const pair<int,int> &to : edges[p.second]) {
			if(!seen[to.first]) {
				q.push({p.first - to.second, to.first});
			}
		}
	}
	return oo;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	vector<vector<pair<int, int>>> edges(n);
	for(int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w; --u, --v; 
		edges[u].push_back({v, w});
		edges[v].push_back({u, w});
	}
	vector<int> special(k);
	for(int &i : special) cin >> i, --i;
	int ans = oo;
	for(clock_t it = clock(); it < 2 * CLOCKS_PER_SEC; it = clock()) {
		shuffle(special.begin(), special.end(), rng);
		vector<int> start[2], end[2];
		for(int i = 0; i < k / 2; ++i) {
			start[rng() & 1].push_back(special[i]);
		}
		for(int i = k / 2; i < k; ++i) {
			end[rng() & 1].push_back(special[i]);
		}
		ans = min(ans, calc(start[0], end[0], edges) + calc(start[1], end[1], edges));
	}
	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1999 ms 396 KB Output is correct
2 Correct 2000 ms 364 KB Output is correct
3 Correct 2000 ms 396 KB Output is correct
4 Correct 2000 ms 392 KB Output is correct
5 Correct 1999 ms 396 KB Output is correct
6 Correct 2000 ms 388 KB Output is correct
7 Correct 2000 ms 364 KB Output is correct
8 Correct 2000 ms 492 KB Output is correct
9 Correct 1999 ms 396 KB Output is correct
10 Correct 2000 ms 396 KB Output is correct
11 Correct 2000 ms 396 KB Output is correct
12 Correct 1999 ms 396 KB Output is correct
13 Correct 2000 ms 452 KB Output is correct
14 Correct 1999 ms 492 KB Output is correct
15 Correct 1999 ms 456 KB Output is correct
16 Correct 1999 ms 492 KB Output is correct
17 Correct 2000 ms 440 KB Output is correct
18 Correct 1999 ms 396 KB Output is correct
19 Correct 2000 ms 492 KB Output is correct
20 Correct 1999 ms 420 KB Output is correct
21 Correct 2000 ms 440 KB Output is correct
22 Correct 1999 ms 396 KB Output is correct
23 Correct 1999 ms 512 KB Output is correct
24 Correct 1999 ms 364 KB Output is correct
25 Correct 2000 ms 364 KB Output is correct
26 Correct 1999 ms 396 KB Output is correct
27 Correct 2000 ms 396 KB Output is correct
28 Correct 1999 ms 456 KB Output is correct
29 Correct 1999 ms 456 KB Output is correct
30 Correct 2000 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1999 ms 396 KB Output is correct
2 Correct 2000 ms 364 KB Output is correct
3 Correct 2000 ms 396 KB Output is correct
4 Correct 2000 ms 392 KB Output is correct
5 Correct 1999 ms 396 KB Output is correct
6 Correct 2000 ms 388 KB Output is correct
7 Correct 2000 ms 364 KB Output is correct
8 Correct 2000 ms 492 KB Output is correct
9 Correct 1999 ms 396 KB Output is correct
10 Correct 2000 ms 396 KB Output is correct
11 Correct 2000 ms 396 KB Output is correct
12 Correct 1999 ms 396 KB Output is correct
13 Correct 2000 ms 452 KB Output is correct
14 Correct 1999 ms 492 KB Output is correct
15 Correct 1999 ms 456 KB Output is correct
16 Correct 1999 ms 492 KB Output is correct
17 Correct 2000 ms 440 KB Output is correct
18 Correct 1999 ms 396 KB Output is correct
19 Correct 2000 ms 492 KB Output is correct
20 Correct 1999 ms 420 KB Output is correct
21 Correct 2000 ms 440 KB Output is correct
22 Correct 1999 ms 396 KB Output is correct
23 Correct 1999 ms 512 KB Output is correct
24 Correct 1999 ms 364 KB Output is correct
25 Correct 2000 ms 364 KB Output is correct
26 Correct 1999 ms 396 KB Output is correct
27 Correct 2000 ms 396 KB Output is correct
28 Correct 1999 ms 456 KB Output is correct
29 Correct 1999 ms 456 KB Output is correct
30 Correct 2000 ms 468 KB Output is correct
31 Correct 2000 ms 428 KB Output is correct
32 Correct 2000 ms 436 KB Output is correct
33 Correct 2000 ms 444 KB Output is correct
34 Correct 1999 ms 424 KB Output is correct
35 Correct 2000 ms 416 KB Output is correct
36 Correct 2000 ms 568 KB Output is correct
37 Correct 2000 ms 652 KB Output is correct
38 Correct 1999 ms 452 KB Output is correct
39 Correct 2000 ms 4212 KB Output is correct
40 Correct 2000 ms 1188 KB Output is correct
41 Correct 2000 ms 456 KB Output is correct
42 Correct 2000 ms 1144 KB Output is correct
43 Correct 2000 ms 532 KB Output is correct
44 Correct 1999 ms 452 KB Output is correct
45 Correct 2000 ms 492 KB Output is correct
46 Correct 2000 ms 3744 KB Output is correct
47 Correct 2000 ms 832 KB Output is correct
48 Correct 2000 ms 3552 KB Output is correct
49 Correct 2000 ms 3720 KB Output is correct
50 Correct 2000 ms 444 KB Output is correct
51 Correct 2000 ms 492 KB Output is correct
52 Correct 2000 ms 492 KB Output is correct
53 Correct 2000 ms 2340 KB Output is correct
54 Correct 2000 ms 3748 KB Output is correct
55 Correct 2000 ms 436 KB Output is correct
56 Correct 1999 ms 424 KB Output is correct
57 Correct 1999 ms 444 KB Output is correct
58 Correct 2001 ms 3664 KB Output is correct
59 Correct 1999 ms 620 KB Output is correct
60 Correct 2000 ms 476 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2005 ms 5812 KB Output is correct
2 Correct 2001 ms 3180 KB Output is correct
3 Correct 2025 ms 75868 KB Output is correct
4 Correct 2044 ms 33508 KB Output is correct
5 Correct 2072 ms 10172 KB Output is correct
6 Correct 2021 ms 8380 KB Output is correct
7 Correct 2039 ms 13576 KB Output is correct
8 Correct 2004 ms 6800 KB Output is correct
9 Correct 2008 ms 9444 KB Output is correct
10 Correct 2004 ms 7592 KB Output is correct
11 Correct 2084 ms 117540 KB Output is correct
12 Correct 2007 ms 8200 KB Output is correct
13 Correct 2045 ms 32576 KB Output is correct
14 Correct 2007 ms 12240 KB Output is correct
15 Correct 2078 ms 115332 KB Output is correct
16 Correct 2001 ms 6124 KB Output is correct
17 Correct 2029 ms 73268 KB Output is correct
18 Correct 2000 ms 3308 KB Output is correct
19 Correct 2025 ms 108340 KB Output is correct
20 Correct 2005 ms 11644 KB Output is correct
21 Correct 2012 ms 11312 KB Output is correct
22 Correct 2005 ms 7376 KB Output is correct
23 Correct 2003 ms 5356 KB Output is correct
24 Correct 2033 ms 93540 KB Output is correct
25 Correct 2005 ms 9708 KB Output is correct
26 Correct 2008 ms 6844 KB Output is correct
27 Correct 2007 ms 8440 KB Output is correct
28 Correct 2001 ms 4332 KB Output is correct
29 Correct 2008 ms 13240 KB Output is correct
30 Correct 2020 ms 21716 KB Output is correct

Subtask #4
58.0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 1999 ms 396 KB Output is correct
2 Correct 2000 ms 364 KB Output is correct
3 Correct 2000 ms 396 KB Output is correct
4 Correct 2000 ms 392 KB Output is correct
5 Correct 1999 ms 396 KB Output is correct
6 Correct 2000 ms 388 KB Output is correct
7 Correct 2000 ms 364 KB Output is correct
8 Correct 2000 ms 492 KB Output is correct
9 Correct 1999 ms 396 KB Output is correct
10 Correct 2000 ms 396 KB Output is correct
11 Correct 2000 ms 396 KB Output is correct
12 Correct 1999 ms 396 KB Output is correct
13 Correct 2000 ms 452 KB Output is correct
14 Correct 1999 ms 492 KB Output is correct
15 Correct 1999 ms 456 KB Output is correct
16 Correct 1999 ms 492 KB Output is correct
17 Correct 2000 ms 440 KB Output is correct
18 Correct 1999 ms 396 KB Output is correct
19 Correct 2000 ms 492 KB Output is correct
20 Correct 1999 ms 420 KB Output is correct
21 Correct 2000 ms 440 KB Output is correct
22 Correct 1999 ms 396 KB Output is correct
23 Correct 1999 ms 512 KB Output is correct
24 Correct 1999 ms 364 KB Output is correct
25 Correct 2000 ms 364 KB Output is correct
26 Correct 1999 ms 396 KB Output is correct
27 Correct 2000 ms 396 KB Output is correct
28 Correct 1999 ms 456 KB Output is correct
29 Correct 1999 ms 456 KB Output is correct
30 Correct 2000 ms 468 KB Output is correct
31 Correct 2000 ms 428 KB Output is correct
32 Correct 2000 ms 436 KB Output is correct
33 Correct 2000 ms 444 KB Output is correct
34 Correct 1999 ms 424 KB Output is correct
35 Correct 2000 ms 416 KB Output is correct
36 Correct 2000 ms 568 KB Output is correct
37 Correct 2000 ms 652 KB Output is correct
38 Correct 1999 ms 452 KB Output is correct
39 Correct 2000 ms 4212 KB Output is correct
40 Correct 2000 ms 1188 KB Output is correct
41 Correct 2000 ms 456 KB Output is correct
42 Correct 2000 ms 1144 KB Output is correct
43 Correct 2000 ms 532 KB Output is correct
44 Correct 1999 ms 452 KB Output is correct
45 Correct 2000 ms 492 KB Output is correct
46 Correct 2000 ms 3744 KB Output is correct
47 Correct 2000 ms 832 KB Output is correct
48 Correct 2000 ms 3552 KB Output is correct
49 Correct 2000 ms 3720 KB Output is correct
50 Correct 2000 ms 444 KB Output is correct
51 Correct 2000 ms 492 KB Output is correct
52 Correct 2000 ms 492 KB Output is correct
53 Correct 2000 ms 2340 KB Output is correct
54 Correct 2000 ms 3748 KB Output is correct
55 Correct 2000 ms 436 KB Output is correct
56 Correct 1999 ms 424 KB Output is correct
57 Correct 1999 ms 444 KB Output is correct
58 Correct 2001 ms 3664 KB Output is correct
59 Correct 1999 ms 620 KB Output is correct
60 Correct 2000 ms 476 KB Output is correct
61 Correct 2005 ms 5812 KB Output is correct
62 Correct 2001 ms 3180 KB Output is correct
63 Correct 2025 ms 75868 KB Output is correct
64 Correct 2044 ms 33508 KB Output is correct
65 Correct 2072 ms 10172 KB Output is correct
66 Correct 2021 ms 8380 KB Output is correct
67 Correct 2039 ms 13576 KB Output is correct
68 Correct 2004 ms 6800 KB Output is correct
69 Correct 2008 ms 9444 KB Output is correct
70 Correct 2004 ms 7592 KB Output is correct
71 Correct 2084 ms 117540 KB Output is correct
72 Correct 2007 ms 8200 KB Output is correct
73 Correct 2045 ms 32576 KB Output is correct
74 Correct 2007 ms 12240 KB Output is correct
75 Correct 2078 ms 115332 KB Output is correct
76 Correct 2001 ms 6124 KB Output is correct
77 Correct 2029 ms 73268 KB Output is correct
78 Correct 2000 ms 3308 KB Output is correct
79 Correct 2025 ms 108340 KB Output is correct
80 Correct 2005 ms 11644 KB Output is correct
81 Correct 2012 ms 11312 KB Output is correct
82 Correct 2005 ms 7376 KB Output is correct
83 Correct 2003 ms 5356 KB Output is correct
84 Correct 2033 ms 93540 KB Output is correct
85 Correct 2005 ms 9708 KB Output is correct
86 Correct 2008 ms 6844 KB Output is correct
87 Correct 2007 ms 8440 KB Output is correct
88 Correct 2001 ms 4332 KB Output is correct
89 Correct 2008 ms 13240 KB Output is correct
90 Correct 2020 ms 21716 KB Output is correct
91 Correct 2017 ms 8888 KB Output is correct
92 Correct 2033 ms 128008 KB Output is correct
93 Correct 2009 ms 13648 KB Output is correct
94 Correct 2021 ms 66816 KB Output is correct
95 Correct 2001 ms 3308 KB Output is correct
96 Correct 2001 ms 3436 KB Output is correct
97 Correct 2016 ms 16384 KB Output is correct
98 Correct 2005 ms 9072 KB Output is correct
99 Correct 2005 ms 9876 KB Output is correct
100 Correct 2039 ms 127780 KB Output is correct
101 Correct 2020 ms 45248 KB Output is correct
102 Correct 2027 ms 44704 KB Output is correct
103 Correct 2098 ms 96124 KB Output is correct
104 Correct 2029 ms 96692 KB Output is correct
105 Correct 2009 ms 6864 KB Output is correct
106 Correct 2063 ms 91172 KB Output is correct
107 Correct 2017 ms 24008 KB Output is correct
108 Correct 2009 ms 11856 KB Output is correct
109 Correct 2001 ms 4716 KB Output is correct
110 Correct 2004 ms 6380 KB Output is correct
111 Correct 2013 ms 12280 KB Output is correct
112 Correct 2065 ms 133880 KB Output is correct
113 Correct 2088 ms 135576 KB Output is correct
114 Correct 2040 ms 12724 KB Output is correct
115 Correct 2050 ms 48636 KB Output is correct
116 Correct 2054 ms 125652 KB Output is correct
117 Correct 2075 ms 94464 KB Output is correct
118 Correct 2037 ms 79376 KB Output is correct
119 Correct 2036 ms 104328 KB Output is correct
120 Correct 2024 ms 58208 KB Output is correct