답안 #377248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377248	2021-03-13T14:22:29 Z	saarang123	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	5568 ms	125840 KB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
const int mxn = 100 * 1000 + 3;
const int inf = 1e9 + 2;
vector<array<int, 2>> g[mxn];
int n, m, k;

int magic(vector<int> &src, vector<int> &snk) {
	priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
	vector<int> dt(n, inf);
	vector<bool> done(n);
	for(int v : src) {
		dt[v] = 0;
		pq.push({0, v});
	}
	for(int &v : snk)
		done[v] = true;
	while(!pq.empty()) {
		auto [wt, v] = pq.top();
		pq.pop();
		if(dt[v] != wt)
			continue;
		if(done[v])
			return wt;
		for(auto &[u, w] : g[v]) {
			if(dt[v] + w < dt[u]) {
				dt[u] = dt[v] + w;
				pq.push({dt[u], u});
			}
		}
	}
	int ret = inf;
	for(int &v : snk)
		ret = min(ret, dt[v]);
	return ret;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    cin >> n >> m >> k;
    for(int u, v, w, i = 0; i < m; i++) {
    	cin >> u >> v >> w;
    	g[--u].push_back({--v, w});
    	g[v].push_back({u, w});
    }
    vector<int> a(k);
    for(int &x : a)
    	cin >> x, x--;
    int ans = inf;
    while(clock() < 5.5 * CLOCKS_PER_SEC) {
    	shuffle(a.begin(), a.end(), rng);
    	vector<int> src[2], snk[2];
    	for(int i = 0; i < k / 2; i++)
    		src[rng() % 2].push_back(a[i]);
    	for(int i = k / 2; i < k; i++) 
    		snk[rng() % 2].push_back(a[i]);
    	ans = min(ans, magic(src[0], snk[0]) + magic(src[1], snk[1]));
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5500 ms	2796 KB	Output is correct
2	Correct	5500 ms	2800 KB	Output is correct
3	Correct	5500 ms	2796 KB	Output is correct
4	Correct	5500 ms	2796 KB	Output is correct
5	Correct	5500 ms	2668 KB	Output is correct
6	Correct	5500 ms	2796 KB	Output is correct
7	Correct	5500 ms	2804 KB	Output is correct
8	Correct	5500 ms	2800 KB	Output is correct
9	Correct	5500 ms	2748 KB	Output is correct
10	Correct	5500 ms	2748 KB	Output is correct
11	Correct	5500 ms	2752 KB	Output is correct
12	Correct	5500 ms	2752 KB	Output is correct
13	Correct	5500 ms	2800 KB	Output is correct
14	Correct	5500 ms	2792 KB	Output is correct
15	Correct	5500 ms	2800 KB	Output is correct
16	Correct	5500 ms	2752 KB	Output is correct
17	Correct	5500 ms	2784 KB	Output is correct
18	Correct	5500 ms	2668 KB	Output is correct
19	Correct	5500 ms	2924 KB	Output is correct
20	Correct	5500 ms	2768 KB	Output is correct
21	Correct	5500 ms	2796 KB	Output is correct
22	Correct	5500 ms	2748 KB	Output is correct
23	Correct	5500 ms	2776 KB	Output is correct
24	Correct	5500 ms	2796 KB	Output is correct
25	Correct	5500 ms	2796 KB	Output is correct
26	Correct	5500 ms	2752 KB	Output is correct
27	Correct	5500 ms	2748 KB	Output is correct
28	Correct	5500 ms	2804 KB	Output is correct
29	Correct	5500 ms	2800 KB	Output is correct
30	Correct	5500 ms	2804 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5500 ms	2796 KB	Output is correct
2	Correct	5500 ms	2800 KB	Output is correct
3	Correct	5500 ms	2796 KB	Output is correct
4	Correct	5500 ms	2796 KB	Output is correct
5	Correct	5500 ms	2668 KB	Output is correct
6	Correct	5500 ms	2796 KB	Output is correct
7	Correct	5500 ms	2804 KB	Output is correct
8	Correct	5500 ms	2800 KB	Output is correct
9	Correct	5500 ms	2748 KB	Output is correct
10	Correct	5500 ms	2748 KB	Output is correct
11	Correct	5500 ms	2752 KB	Output is correct
12	Correct	5500 ms	2752 KB	Output is correct
13	Correct	5500 ms	2800 KB	Output is correct
14	Correct	5500 ms	2792 KB	Output is correct
15	Correct	5500 ms	2800 KB	Output is correct
16	Correct	5500 ms	2752 KB	Output is correct
17	Correct	5500 ms	2784 KB	Output is correct
18	Correct	5500 ms	2668 KB	Output is correct
19	Correct	5500 ms	2924 KB	Output is correct
20	Correct	5500 ms	2768 KB	Output is correct
21	Correct	5500 ms	2796 KB	Output is correct
22	Correct	5500 ms	2748 KB	Output is correct
23	Correct	5500 ms	2776 KB	Output is correct
24	Correct	5500 ms	2796 KB	Output is correct
25	Correct	5500 ms	2796 KB	Output is correct
26	Correct	5500 ms	2752 KB	Output is correct
27	Correct	5500 ms	2748 KB	Output is correct
28	Correct	5500 ms	2804 KB	Output is correct
29	Correct	5500 ms	2800 KB	Output is correct
30	Correct	5500 ms	2804 KB	Output is correct
31	Correct	5500 ms	2744 KB	Output is correct
32	Correct	5500 ms	2796 KB	Output is correct
33	Correct	5500 ms	2796 KB	Output is correct
34	Correct	5500 ms	2796 KB	Output is correct
35	Correct	5500 ms	2884 KB	Output is correct
36	Correct	5500 ms	3052 KB	Output is correct
37	Correct	5500 ms	3052 KB	Output is correct
38	Correct	5500 ms	2924 KB	Output is correct
39	Correct	5500 ms	6124 KB	Output is correct
40	Correct	5500 ms	3568 KB	Output is correct
41	Correct	5500 ms	2804 KB	Output is correct
42	Correct	5500 ms	3564 KB	Output is correct
43	Correct	5500 ms	2924 KB	Output is correct
44	Correct	5500 ms	2804 KB	Output is correct
45	Correct	5500 ms	2764 KB	Output is correct
46	Correct	5500 ms	6284 KB	Output is correct
47	Correct	5500 ms	3240 KB	Output is correct
48	Correct	5500 ms	5916 KB	Output is correct
49	Correct	5500 ms	6040 KB	Output is correct
50	Correct	5500 ms	2668 KB	Output is correct
51	Correct	5500 ms	2796 KB	Output is correct
52	Correct	5500 ms	2792 KB	Output is correct
53	Correct	5500 ms	4460 KB	Output is correct
54	Correct	5500 ms	6080 KB	Output is correct
55	Correct	5500 ms	2796 KB	Output is correct
56	Correct	5500 ms	2796 KB	Output is correct
57	Correct	5500 ms	2668 KB	Output is correct
58	Correct	5500 ms	6124 KB	Output is correct
59	Correct	5500 ms	2752 KB	Output is correct
60	Correct	5500 ms	2820 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5505 ms	7020 KB	Output is correct
2	Correct	5501 ms	3820 KB	Output is correct
3	Correct	5559 ms	66004 KB	Output is correct
4	Correct	5531 ms	34380 KB	Output is correct
5	Correct	5524 ms	10972 KB	Output is correct
6	Correct	5515 ms	9220 KB	Output is correct
7	Correct	5512 ms	11740 KB	Output is correct
8	Correct	5506 ms	7048 KB	Output is correct
9	Correct	5527 ms	9316 KB	Output is correct
10	Correct	5508 ms	7664 KB	Output is correct
11	Correct	5536 ms	68092 KB	Output is correct
12	Correct	5504 ms	7912 KB	Output is correct
13	Correct	5544 ms	23324 KB	Output is correct
14	Correct	5510 ms	10764 KB	Output is correct
15	Correct	5568 ms	66972 KB	Output is correct
16	Correct	5505 ms	6548 KB	Output is correct
17	Correct	5529 ms	48636 KB	Output is correct
18	Correct	5501 ms	3812 KB	Output is correct
19	Correct	5536 ms	67252 KB	Output is correct
20	Correct	5507 ms	9984 KB	Output is correct
21	Correct	5508 ms	10232 KB	Output is correct
22	Correct	5504 ms	7212 KB	Output is correct
23	Correct	5503 ms	5716 KB	Output is correct
24	Correct	5561 ms	57308 KB	Output is correct
25	Correct	5506 ms	7956 KB	Output is correct
26	Correct	5504 ms	5988 KB	Output is correct
27	Correct	5511 ms	7140 KB	Output is correct
28	Correct	5502 ms	4376 KB	Output is correct
29	Correct	5512 ms	10176 KB	Output is correct
30	Correct	5522 ms	21896 KB	Output is correct

Subtask #4
58.0 / 58.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5500 ms	2796 KB	Output is correct
2	Correct	5500 ms	2800 KB	Output is correct
3	Correct	5500 ms	2796 KB	Output is correct
4	Correct	5500 ms	2796 KB	Output is correct
5	Correct	5500 ms	2668 KB	Output is correct
6	Correct	5500 ms	2796 KB	Output is correct
7	Correct	5500 ms	2804 KB	Output is correct
8	Correct	5500 ms	2800 KB	Output is correct
9	Correct	5500 ms	2748 KB	Output is correct
10	Correct	5500 ms	2748 KB	Output is correct
11	Correct	5500 ms	2752 KB	Output is correct
12	Correct	5500 ms	2752 KB	Output is correct
13	Correct	5500 ms	2800 KB	Output is correct
14	Correct	5500 ms	2792 KB	Output is correct
15	Correct	5500 ms	2800 KB	Output is correct
16	Correct	5500 ms	2752 KB	Output is correct
17	Correct	5500 ms	2784 KB	Output is correct
18	Correct	5500 ms	2668 KB	Output is correct
19	Correct	5500 ms	2924 KB	Output is correct
20	Correct	5500 ms	2768 KB	Output is correct
21	Correct	5500 ms	2796 KB	Output is correct
22	Correct	5500 ms	2748 KB	Output is correct
23	Correct	5500 ms	2776 KB	Output is correct
24	Correct	5500 ms	2796 KB	Output is correct
25	Correct	5500 ms	2796 KB	Output is correct
26	Correct	5500 ms	2752 KB	Output is correct
27	Correct	5500 ms	2748 KB	Output is correct
28	Correct	5500 ms	2804 KB	Output is correct
29	Correct	5500 ms	2800 KB	Output is correct
30	Correct	5500 ms	2804 KB	Output is correct
31	Correct	5500 ms	2744 KB	Output is correct
32	Correct	5500 ms	2796 KB	Output is correct
33	Correct	5500 ms	2796 KB	Output is correct
34	Correct	5500 ms	2796 KB	Output is correct
35	Correct	5500 ms	2884 KB	Output is correct
36	Correct	5500 ms	3052 KB	Output is correct
37	Correct	5500 ms	3052 KB	Output is correct
38	Correct	5500 ms	2924 KB	Output is correct
39	Correct	5500 ms	6124 KB	Output is correct
40	Correct	5500 ms	3568 KB	Output is correct
41	Correct	5500 ms	2804 KB	Output is correct
42	Correct	5500 ms	3564 KB	Output is correct
43	Correct	5500 ms	2924 KB	Output is correct
44	Correct	5500 ms	2804 KB	Output is correct
45	Correct	5500 ms	2764 KB	Output is correct
46	Correct	5500 ms	6284 KB	Output is correct
47	Correct	5500 ms	3240 KB	Output is correct
48	Correct	5500 ms	5916 KB	Output is correct
49	Correct	5500 ms	6040 KB	Output is correct
50	Correct	5500 ms	2668 KB	Output is correct
51	Correct	5500 ms	2796 KB	Output is correct
52	Correct	5500 ms	2792 KB	Output is correct
53	Correct	5500 ms	4460 KB	Output is correct
54	Correct	5500 ms	6080 KB	Output is correct
55	Correct	5500 ms	2796 KB	Output is correct
56	Correct	5500 ms	2796 KB	Output is correct
57	Correct	5500 ms	2668 KB	Output is correct
58	Correct	5500 ms	6124 KB	Output is correct
59	Correct	5500 ms	2752 KB	Output is correct
60	Correct	5500 ms	2820 KB	Output is correct
61	Correct	5505 ms	7020 KB	Output is correct
62	Correct	5501 ms	3820 KB	Output is correct
63	Correct	5559 ms	66004 KB	Output is correct
64	Correct	5531 ms	34380 KB	Output is correct
65	Correct	5524 ms	10972 KB	Output is correct
66	Correct	5515 ms	9220 KB	Output is correct
67	Correct	5512 ms	11740 KB	Output is correct
68	Correct	5506 ms	7048 KB	Output is correct
69	Correct	5527 ms	9316 KB	Output is correct
70	Correct	5508 ms	7664 KB	Output is correct
71	Correct	5536 ms	68092 KB	Output is correct
72	Correct	5504 ms	7912 KB	Output is correct
73	Correct	5544 ms	23324 KB	Output is correct
74	Correct	5510 ms	10764 KB	Output is correct
75	Correct	5568 ms	66972 KB	Output is correct
76	Correct	5505 ms	6548 KB	Output is correct
77	Correct	5529 ms	48636 KB	Output is correct
78	Correct	5501 ms	3812 KB	Output is correct
79	Correct	5536 ms	67252 KB	Output is correct
80	Correct	5507 ms	9984 KB	Output is correct
81	Correct	5508 ms	10232 KB	Output is correct
82	Correct	5504 ms	7212 KB	Output is correct
83	Correct	5503 ms	5716 KB	Output is correct
84	Correct	5561 ms	57308 KB	Output is correct
85	Correct	5506 ms	7956 KB	Output is correct
86	Correct	5504 ms	5988 KB	Output is correct
87	Correct	5511 ms	7140 KB	Output is correct
88	Correct	5502 ms	4376 KB	Output is correct
89	Correct	5512 ms	10176 KB	Output is correct
90	Correct	5522 ms	21896 KB	Output is correct
91	Correct	5539 ms	9980 KB	Output is correct
92	Correct	5550 ms	117332 KB	Output is correct
93	Correct	5507 ms	13628 KB	Output is correct
94	Correct	5528 ms	67712 KB	Output is correct
95	Correct	5501 ms	3804 KB	Output is correct
96	Correct	5501 ms	3944 KB	Output is correct
97	Correct	5512 ms	17120 KB	Output is correct
98	Correct	5519 ms	9240 KB	Output is correct
99	Correct	5511 ms	10352 KB	Output is correct
100	Correct	5552 ms	124484 KB	Output is correct
101	Correct	5522 ms	45492 KB	Output is correct
102	Correct	5522 ms	44888 KB	Output is correct
103	Correct	5533 ms	87148 KB	Output is correct
104	Correct	5526 ms	95720 KB	Output is correct
105	Correct	5504 ms	7244 KB	Output is correct
106	Correct	5545 ms	87320 KB	Output is correct
107	Correct	5524 ms	24580 KB	Output is correct
108	Correct	5509 ms	12556 KB	Output is correct
109	Correct	5502 ms	5220 KB	Output is correct
110	Correct	5504 ms	6816 KB	Output is correct
111	Correct	5509 ms	12760 KB	Output is correct
112	Correct	5541 ms	125216 KB	Output is correct
113	Correct	5552 ms	125840 KB	Output is correct
114	Correct	5531 ms	12692 KB	Output is correct
115	Correct	5559 ms	45508 KB	Output is correct
116	Correct	5538 ms	114592 KB	Output is correct
117	Correct	5566 ms	85308 KB	Output is correct
118	Correct	5538 ms	75868 KB	Output is correct
119	Correct	5546 ms	101540 KB	Output is correct
120	Correct	5521 ms	58608 KB	Output is correct

답안 #377248

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 12.0 / 12.0

Subtask #3 25.0 / 25.0

Subtask #4 58.0 / 58.0

Subtask #1
5.0 / 5.0

Subtask #2
12.0 / 12.0

Subtask #3
25.0 / 25.0

Subtask #4
58.0 / 58.0