답안 #377242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377242	2021-03-13T14:14:17 Z	saarang123	Relay Marathon (NOI20_relaymarathon)	C++17	17 / 100	5836 ms	112040 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);
	for(int v : src) {
		dt[v] = 0;
		pq.push({0, v});
	}
	while(!pq.empty()) {
		auto [wt, v] = pq.top();
		pq.pop();
		if(dt[v] != wt)
			continue;
		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.7 * 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	5700 ms	2752 KB	Output is correct
2	Correct	5700 ms	2800 KB	Output is correct
3	Correct	5700 ms	2752 KB	Output is correct
4	Correct	5700 ms	2748 KB	Output is correct
5	Correct	5700 ms	2752 KB	Output is correct
6	Correct	5700 ms	2752 KB	Output is correct
7	Correct	5700 ms	2804 KB	Output is correct
8	Correct	5700 ms	2924 KB	Output is correct
9	Correct	5700 ms	2748 KB	Output is correct
10	Correct	5700 ms	2748 KB	Output is correct
11	Correct	5700 ms	2752 KB	Output is correct
12	Correct	5700 ms	2752 KB	Output is correct
13	Correct	5700 ms	2796 KB	Output is correct
14	Correct	5700 ms	2796 KB	Output is correct
15	Correct	5700 ms	2800 KB	Output is correct
16	Correct	5700 ms	2752 KB	Output is correct
17	Correct	5700 ms	2784 KB	Output is correct
18	Correct	5700 ms	2752 KB	Output is correct
19	Correct	5700 ms	2804 KB	Output is correct
20	Correct	5700 ms	2768 KB	Output is correct
21	Correct	5700 ms	2796 KB	Output is correct
22	Correct	5700 ms	2748 KB	Output is correct
23	Correct	5700 ms	2776 KB	Output is correct
24	Correct	5700 ms	2752 KB	Output is correct
25	Correct	5700 ms	2796 KB	Output is correct
26	Correct	5700 ms	2752 KB	Output is correct
27	Correct	5700 ms	2748 KB	Output is correct
28	Correct	5700 ms	2804 KB	Output is correct
29	Correct	5700 ms	2924 KB	Output is correct
30	Correct	5700 ms	2804 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5700 ms	2752 KB	Output is correct
2	Correct	5700 ms	2800 KB	Output is correct
3	Correct	5700 ms	2752 KB	Output is correct
4	Correct	5700 ms	2748 KB	Output is correct
5	Correct	5700 ms	2752 KB	Output is correct
6	Correct	5700 ms	2752 KB	Output is correct
7	Correct	5700 ms	2804 KB	Output is correct
8	Correct	5700 ms	2924 KB	Output is correct
9	Correct	5700 ms	2748 KB	Output is correct
10	Correct	5700 ms	2748 KB	Output is correct
11	Correct	5700 ms	2752 KB	Output is correct
12	Correct	5700 ms	2752 KB	Output is correct
13	Correct	5700 ms	2796 KB	Output is correct
14	Correct	5700 ms	2796 KB	Output is correct
15	Correct	5700 ms	2800 KB	Output is correct
16	Correct	5700 ms	2752 KB	Output is correct
17	Correct	5700 ms	2784 KB	Output is correct
18	Correct	5700 ms	2752 KB	Output is correct
19	Correct	5700 ms	2804 KB	Output is correct
20	Correct	5700 ms	2768 KB	Output is correct
21	Correct	5700 ms	2796 KB	Output is correct
22	Correct	5700 ms	2748 KB	Output is correct
23	Correct	5700 ms	2776 KB	Output is correct
24	Correct	5700 ms	2752 KB	Output is correct
25	Correct	5700 ms	2796 KB	Output is correct
26	Correct	5700 ms	2752 KB	Output is correct
27	Correct	5700 ms	2748 KB	Output is correct
28	Correct	5700 ms	2804 KB	Output is correct
29	Correct	5700 ms	2924 KB	Output is correct
30	Correct	5700 ms	2804 KB	Output is correct
31	Correct	5700 ms	2796 KB	Output is correct
32	Correct	5700 ms	2796 KB	Output is correct
33	Correct	5700 ms	2792 KB	Output is correct
34	Correct	5700 ms	2668 KB	Output is correct
35	Correct	5700 ms	2756 KB	Output is correct
36	Correct	5700 ms	3052 KB	Output is correct
37	Correct	5700 ms	3052 KB	Output is correct
38	Correct	5700 ms	2924 KB	Output is correct
39	Correct	5701 ms	6124 KB	Output is correct
40	Correct	5700 ms	3512 KB	Output is correct
41	Correct	5700 ms	2804 KB	Output is correct
42	Correct	5700 ms	3528 KB	Output is correct
43	Correct	5700 ms	2896 KB	Output is correct
44	Correct	5700 ms	2924 KB	Output is correct
45	Correct	5700 ms	2764 KB	Output is correct
46	Correct	5701 ms	6304 KB	Output is correct
47	Correct	5701 ms	3240 KB	Output is correct
48	Correct	5702 ms	5932 KB	Output is correct
49	Correct	5701 ms	6056 KB	Output is correct
50	Correct	5700 ms	2792 KB	Output is correct
51	Correct	5700 ms	2808 KB	Output is correct
52	Correct	5700 ms	2792 KB	Output is correct
53	Correct	5701 ms	4484 KB	Output is correct
54	Correct	5700 ms	6100 KB	Output is correct
55	Correct	5700 ms	2780 KB	Output is correct
56	Correct	5700 ms	2668 KB	Output is correct
57	Correct	5700 ms	2668 KB	Output is correct
58	Correct	5701 ms	6380 KB	Output is correct
59	Correct	5700 ms	2796 KB	Output is correct
60	Correct	5700 ms	2820 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5713 ms	7284 KB	Output is correct
2	Correct	5701 ms	4196 KB	Output is correct
3	Correct	5820 ms	103876 KB	Output is correct
4	Correct	5767 ms	48816 KB	Output is correct
5	Correct	5740 ms	12552 KB	Output is correct
6	Correct	5775 ms	10384 KB	Output is correct
7	Correct	5789 ms	13768 KB	Output is correct
8	Correct	5716 ms	7156 KB	Output is correct
9	Correct	5747 ms	9848 KB	Output is correct
10	Correct	5721 ms	7944 KB	Output is correct
11	Correct	5827 ms	110216 KB	Output is correct
12	Correct	5723 ms	8504 KB	Output is correct
13	Correct	5721 ms	32656 KB	Output is correct
14	Correct	5781 ms	13764 KB	Output is correct
15	Correct	5775 ms	108212 KB	Output is correct
16	Correct	5715 ms	6628 KB	Output is correct
17	Correct	5778 ms	74972 KB	Output is correct
18	Correct	5701 ms	4164 KB	Output is correct
19	Correct	5757 ms	112040 KB	Output is correct
20	Correct	5789 ms	13112 KB	Output is correct
21	Correct	5723 ms	11860 KB	Output is correct
22	Correct	5742 ms	7996 KB	Output is correct
23	Correct	5703 ms	6124 KB	Output is correct
24	Correct	5836 ms	84424 KB	Output is correct
25	Correct	5725 ms	9812 KB	Output is correct
26	Correct	5715 ms	7020 KB	Output is correct
27	Correct	5760 ms	8684 KB	Output is correct
28	Correct	5702 ms	5092 KB	Output is correct
29	Incorrect	5795 ms	13136 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 58.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5700 ms	2752 KB	Output is correct
2	Correct	5700 ms	2800 KB	Output is correct
3	Correct	5700 ms	2752 KB	Output is correct
4	Correct	5700 ms	2748 KB	Output is correct
5	Correct	5700 ms	2752 KB	Output is correct
6	Correct	5700 ms	2752 KB	Output is correct
7	Correct	5700 ms	2804 KB	Output is correct
8	Correct	5700 ms	2924 KB	Output is correct
9	Correct	5700 ms	2748 KB	Output is correct
10	Correct	5700 ms	2748 KB	Output is correct
11	Correct	5700 ms	2752 KB	Output is correct
12	Correct	5700 ms	2752 KB	Output is correct
13	Correct	5700 ms	2796 KB	Output is correct
14	Correct	5700 ms	2796 KB	Output is correct
15	Correct	5700 ms	2800 KB	Output is correct
16	Correct	5700 ms	2752 KB	Output is correct
17	Correct	5700 ms	2784 KB	Output is correct
18	Correct	5700 ms	2752 KB	Output is correct
19	Correct	5700 ms	2804 KB	Output is correct
20	Correct	5700 ms	2768 KB	Output is correct
21	Correct	5700 ms	2796 KB	Output is correct
22	Correct	5700 ms	2748 KB	Output is correct
23	Correct	5700 ms	2776 KB	Output is correct
24	Correct	5700 ms	2752 KB	Output is correct
25	Correct	5700 ms	2796 KB	Output is correct
26	Correct	5700 ms	2752 KB	Output is correct
27	Correct	5700 ms	2748 KB	Output is correct
28	Correct	5700 ms	2804 KB	Output is correct
29	Correct	5700 ms	2924 KB	Output is correct
30	Correct	5700 ms	2804 KB	Output is correct
31	Correct	5700 ms	2796 KB	Output is correct
32	Correct	5700 ms	2796 KB	Output is correct
33	Correct	5700 ms	2792 KB	Output is correct
34	Correct	5700 ms	2668 KB	Output is correct
35	Correct	5700 ms	2756 KB	Output is correct
36	Correct	5700 ms	3052 KB	Output is correct
37	Correct	5700 ms	3052 KB	Output is correct
38	Correct	5700 ms	2924 KB	Output is correct
39	Correct	5701 ms	6124 KB	Output is correct
40	Correct	5700 ms	3512 KB	Output is correct
41	Correct	5700 ms	2804 KB	Output is correct
42	Correct	5700 ms	3528 KB	Output is correct
43	Correct	5700 ms	2896 KB	Output is correct
44	Correct	5700 ms	2924 KB	Output is correct
45	Correct	5700 ms	2764 KB	Output is correct
46	Correct	5701 ms	6304 KB	Output is correct
47	Correct	5701 ms	3240 KB	Output is correct
48	Correct	5702 ms	5932 KB	Output is correct
49	Correct	5701 ms	6056 KB	Output is correct
50	Correct	5700 ms	2792 KB	Output is correct
51	Correct	5700 ms	2808 KB	Output is correct
52	Correct	5700 ms	2792 KB	Output is correct
53	Correct	5701 ms	4484 KB	Output is correct
54	Correct	5700 ms	6100 KB	Output is correct
55	Correct	5700 ms	2780 KB	Output is correct
56	Correct	5700 ms	2668 KB	Output is correct
57	Correct	5700 ms	2668 KB	Output is correct
58	Correct	5701 ms	6380 KB	Output is correct
59	Correct	5700 ms	2796 KB	Output is correct
60	Correct	5700 ms	2820 KB	Output is correct
61	Correct	5713 ms	7284 KB	Output is correct
62	Correct	5701 ms	4196 KB	Output is correct
63	Correct	5820 ms	103876 KB	Output is correct
64	Correct	5767 ms	48816 KB	Output is correct
65	Correct	5740 ms	12552 KB	Output is correct
66	Correct	5775 ms	10384 KB	Output is correct
67	Correct	5789 ms	13768 KB	Output is correct
68	Correct	5716 ms	7156 KB	Output is correct
69	Correct	5747 ms	9848 KB	Output is correct
70	Correct	5721 ms	7944 KB	Output is correct
71	Correct	5827 ms	110216 KB	Output is correct
72	Correct	5723 ms	8504 KB	Output is correct
73	Correct	5721 ms	32656 KB	Output is correct
74	Correct	5781 ms	13764 KB	Output is correct
75	Correct	5775 ms	108212 KB	Output is correct
76	Correct	5715 ms	6628 KB	Output is correct
77	Correct	5778 ms	74972 KB	Output is correct
78	Correct	5701 ms	4164 KB	Output is correct
79	Correct	5757 ms	112040 KB	Output is correct
80	Correct	5789 ms	13112 KB	Output is correct
81	Correct	5723 ms	11860 KB	Output is correct
82	Correct	5742 ms	7996 KB	Output is correct
83	Correct	5703 ms	6124 KB	Output is correct
84	Correct	5836 ms	84424 KB	Output is correct
85	Correct	5725 ms	9812 KB	Output is correct
86	Correct	5715 ms	7020 KB	Output is correct
87	Correct	5760 ms	8684 KB	Output is correct
88	Correct	5702 ms	5092 KB	Output is correct
89	Incorrect	5795 ms	13136 KB	Output isn't correct
90	Halted	0 ms	0 KB	-

답안 #377242

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 25.0

Subtask #4 0 / 58.0

Subtask #1
5.0 / 5.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 25.0

Subtask #4
0 / 58.0