답안 #379947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379947	2021-03-19T19:12:56 Z	nikatamliani	Relay Marathon (NOI20_relaymarathon)	C++14	100 / 100	5097 ms	90672 KB

RelayMarathon

#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 < 5 * 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

#	결과	실행 시간	메모리	Grader output
1	Correct	4999 ms	396 KB	Output is correct
2	Correct	4999 ms	456 KB	Output is correct
3	Correct	4999 ms	396 KB	Output is correct
4	Correct	5000 ms	492 KB	Output is correct
5	Correct	5000 ms	396 KB	Output is correct
6	Correct	4999 ms	396 KB	Output is correct
7	Correct	5000 ms	456 KB	Output is correct
8	Correct	5000 ms	492 KB	Output is correct
9	Correct	5000 ms	396 KB	Output is correct
10	Correct	5000 ms	396 KB	Output is correct
11	Correct	4999 ms	492 KB	Output is correct
12	Correct	5000 ms	396 KB	Output is correct
13	Correct	4999 ms	452 KB	Output is correct
14	Correct	4999 ms	448 KB	Output is correct
15	Correct	4999 ms	456 KB	Output is correct
16	Correct	4999 ms	396 KB	Output is correct
17	Correct	5000 ms	440 KB	Output is correct
18	Correct	5000 ms	396 KB	Output is correct
19	Correct	5000 ms	456 KB	Output is correct
20	Correct	5000 ms	420 KB	Output is correct
21	Correct	5000 ms	440 KB	Output is correct
22	Correct	4999 ms	396 KB	Output is correct
23	Correct	4999 ms	428 KB	Output is correct
24	Correct	5000 ms	396 KB	Output is correct
25	Correct	5000 ms	396 KB	Output is correct
26	Correct	5000 ms	512 KB	Output is correct
27	Correct	5000 ms	396 KB	Output is correct
28	Correct	5000 ms	364 KB	Output is correct
29	Correct	5000 ms	456 KB	Output is correct
30	Correct	5000 ms	364 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4999 ms	396 KB	Output is correct
2	Correct	4999 ms	456 KB	Output is correct
3	Correct	4999 ms	396 KB	Output is correct
4	Correct	5000 ms	492 KB	Output is correct
5	Correct	5000 ms	396 KB	Output is correct
6	Correct	4999 ms	396 KB	Output is correct
7	Correct	5000 ms	456 KB	Output is correct
8	Correct	5000 ms	492 KB	Output is correct
9	Correct	5000 ms	396 KB	Output is correct
10	Correct	5000 ms	396 KB	Output is correct
11	Correct	4999 ms	492 KB	Output is correct
12	Correct	5000 ms	396 KB	Output is correct
13	Correct	4999 ms	452 KB	Output is correct
14	Correct	4999 ms	448 KB	Output is correct
15	Correct	4999 ms	456 KB	Output is correct
16	Correct	4999 ms	396 KB	Output is correct
17	Correct	5000 ms	440 KB	Output is correct
18	Correct	5000 ms	396 KB	Output is correct
19	Correct	5000 ms	456 KB	Output is correct
20	Correct	5000 ms	420 KB	Output is correct
21	Correct	5000 ms	440 KB	Output is correct
22	Correct	4999 ms	396 KB	Output is correct
23	Correct	4999 ms	428 KB	Output is correct
24	Correct	5000 ms	396 KB	Output is correct
25	Correct	5000 ms	396 KB	Output is correct
26	Correct	5000 ms	512 KB	Output is correct
27	Correct	5000 ms	396 KB	Output is correct
28	Correct	5000 ms	364 KB	Output is correct
29	Correct	5000 ms	456 KB	Output is correct
30	Correct	5000 ms	364 KB	Output is correct
31	Correct	5000 ms	428 KB	Output is correct
32	Correct	4999 ms	436 KB	Output is correct
33	Correct	5000 ms	444 KB	Output is correct
34	Correct	5000 ms	424 KB	Output is correct
35	Correct	4999 ms	416 KB	Output is correct
36	Correct	5000 ms	568 KB	Output is correct
37	Correct	5005 ms	652 KB	Output is correct
38	Correct	5000 ms	452 KB	Output is correct
39	Correct	5000 ms	4612 KB	Output is correct
40	Correct	5000 ms	1064 KB	Output is correct
41	Correct	4999 ms	364 KB	Output is correct
42	Correct	5000 ms	1144 KB	Output is correct
43	Correct	5000 ms	532 KB	Output is correct
44	Correct	5000 ms	452 KB	Output is correct
45	Correct	4999 ms	364 KB	Output is correct
46	Correct	5001 ms	4024 KB	Output is correct
47	Correct	5000 ms	876 KB	Output is correct
48	Correct	5000 ms	3756 KB	Output is correct
49	Correct	5001 ms	3624 KB	Output is correct
50	Correct	4999 ms	444 KB	Output is correct
51	Correct	5000 ms	492 KB	Output is correct
52	Correct	4999 ms	492 KB	Output is correct
53	Correct	5000 ms	2800 KB	Output is correct
54	Correct	5000 ms	4132 KB	Output is correct
55	Correct	4999 ms	436 KB	Output is correct
56	Correct	5000 ms	428 KB	Output is correct
57	Correct	5000 ms	364 KB	Output is correct
58	Correct	5001 ms	3984 KB	Output is correct
59	Correct	4999 ms	416 KB	Output is correct
60	Correct	5000 ms	492 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5006 ms	6028 KB	Output is correct
2	Correct	5001 ms	3308 KB	Output is correct
3	Correct	5086 ms	76508 KB	Output is correct
4	Correct	5021 ms	34204 KB	Output is correct
5	Correct	5017 ms	10784 KB	Output is correct
6	Correct	5005 ms	8868 KB	Output is correct
7	Correct	5019 ms	11620 KB	Output is correct
8	Correct	5010 ms	6960 KB	Output is correct
9	Correct	5005 ms	8820 KB	Output is correct
10	Correct	5009 ms	7020 KB	Output is correct
11	Correct	5041 ms	77604 KB	Output is correct
12	Correct	5009 ms	7812 KB	Output is correct
13	Correct	5044 ms	24216 KB	Output is correct
14	Correct	5008 ms	10400 KB	Output is correct
15	Correct	5051 ms	76312 KB	Output is correct
16	Correct	5004 ms	6124 KB	Output is correct
17	Correct	5035 ms	49404 KB	Output is correct
18	Correct	5001 ms	3404 KB	Output is correct
19	Correct	5037 ms	68012 KB	Output is correct
20	Correct	5007 ms	10036 KB	Output is correct
21	Correct	5013 ms	10172 KB	Output is correct
22	Correct	5004 ms	7180 KB	Output is correct
23	Correct	5003 ms	5228 KB	Output is correct
24	Correct	5097 ms	66760 KB	Output is correct
25	Correct	5008 ms	8664 KB	Output is correct
26	Correct	5004 ms	6752 KB	Output is correct
27	Correct	5004 ms	7672 KB	Output is correct
28	Correct	5002 ms	4332 KB	Output is correct
29	Correct	5007 ms	11252 KB	Output is correct
30	Correct	5017 ms	16072 KB	Output is correct

Subtask #4
58.0 / 58.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4999 ms	396 KB	Output is correct
2	Correct	4999 ms	456 KB	Output is correct
3	Correct	4999 ms	396 KB	Output is correct
4	Correct	5000 ms	492 KB	Output is correct
5	Correct	5000 ms	396 KB	Output is correct
6	Correct	4999 ms	396 KB	Output is correct
7	Correct	5000 ms	456 KB	Output is correct
8	Correct	5000 ms	492 KB	Output is correct
9	Correct	5000 ms	396 KB	Output is correct
10	Correct	5000 ms	396 KB	Output is correct
11	Correct	4999 ms	492 KB	Output is correct
12	Correct	5000 ms	396 KB	Output is correct
13	Correct	4999 ms	452 KB	Output is correct
14	Correct	4999 ms	448 KB	Output is correct
15	Correct	4999 ms	456 KB	Output is correct
16	Correct	4999 ms	396 KB	Output is correct
17	Correct	5000 ms	440 KB	Output is correct
18	Correct	5000 ms	396 KB	Output is correct
19	Correct	5000 ms	456 KB	Output is correct
20	Correct	5000 ms	420 KB	Output is correct
21	Correct	5000 ms	440 KB	Output is correct
22	Correct	4999 ms	396 KB	Output is correct
23	Correct	4999 ms	428 KB	Output is correct
24	Correct	5000 ms	396 KB	Output is correct
25	Correct	5000 ms	396 KB	Output is correct
26	Correct	5000 ms	512 KB	Output is correct
27	Correct	5000 ms	396 KB	Output is correct
28	Correct	5000 ms	364 KB	Output is correct
29	Correct	5000 ms	456 KB	Output is correct
30	Correct	5000 ms	364 KB	Output is correct
31	Correct	5000 ms	428 KB	Output is correct
32	Correct	4999 ms	436 KB	Output is correct
33	Correct	5000 ms	444 KB	Output is correct
34	Correct	5000 ms	424 KB	Output is correct
35	Correct	4999 ms	416 KB	Output is correct
36	Correct	5000 ms	568 KB	Output is correct
37	Correct	5005 ms	652 KB	Output is correct
38	Correct	5000 ms	452 KB	Output is correct
39	Correct	5000 ms	4612 KB	Output is correct
40	Correct	5000 ms	1064 KB	Output is correct
41	Correct	4999 ms	364 KB	Output is correct
42	Correct	5000 ms	1144 KB	Output is correct
43	Correct	5000 ms	532 KB	Output is correct
44	Correct	5000 ms	452 KB	Output is correct
45	Correct	4999 ms	364 KB	Output is correct
46	Correct	5001 ms	4024 KB	Output is correct
47	Correct	5000 ms	876 KB	Output is correct
48	Correct	5000 ms	3756 KB	Output is correct
49	Correct	5001 ms	3624 KB	Output is correct
50	Correct	4999 ms	444 KB	Output is correct
51	Correct	5000 ms	492 KB	Output is correct
52	Correct	4999 ms	492 KB	Output is correct
53	Correct	5000 ms	2800 KB	Output is correct
54	Correct	5000 ms	4132 KB	Output is correct
55	Correct	4999 ms	436 KB	Output is correct
56	Correct	5000 ms	428 KB	Output is correct
57	Correct	5000 ms	364 KB	Output is correct
58	Correct	5001 ms	3984 KB	Output is correct
59	Correct	4999 ms	416 KB	Output is correct
60	Correct	5000 ms	492 KB	Output is correct
61	Correct	5006 ms	6028 KB	Output is correct
62	Correct	5001 ms	3308 KB	Output is correct
63	Correct	5086 ms	76508 KB	Output is correct
64	Correct	5021 ms	34204 KB	Output is correct
65	Correct	5017 ms	10784 KB	Output is correct
66	Correct	5005 ms	8868 KB	Output is correct
67	Correct	5019 ms	11620 KB	Output is correct
68	Correct	5010 ms	6960 KB	Output is correct
69	Correct	5005 ms	8820 KB	Output is correct
70	Correct	5009 ms	7020 KB	Output is correct
71	Correct	5041 ms	77604 KB	Output is correct
72	Correct	5009 ms	7812 KB	Output is correct
73	Correct	5044 ms	24216 KB	Output is correct
74	Correct	5008 ms	10400 KB	Output is correct
75	Correct	5051 ms	76312 KB	Output is correct
76	Correct	5004 ms	6124 KB	Output is correct
77	Correct	5035 ms	49404 KB	Output is correct
78	Correct	5001 ms	3404 KB	Output is correct
79	Correct	5037 ms	68012 KB	Output is correct
80	Correct	5007 ms	10036 KB	Output is correct
81	Correct	5013 ms	10172 KB	Output is correct
82	Correct	5004 ms	7180 KB	Output is correct
83	Correct	5003 ms	5228 KB	Output is correct
84	Correct	5097 ms	66760 KB	Output is correct
85	Correct	5008 ms	8664 KB	Output is correct
86	Correct	5004 ms	6752 KB	Output is correct
87	Correct	5004 ms	7672 KB	Output is correct
88	Correct	5002 ms	4332 KB	Output is correct
89	Correct	5007 ms	11252 KB	Output is correct
90	Correct	5017 ms	16072 KB	Output is correct
91	Correct	5030 ms	8432 KB	Output is correct
92	Correct	5075 ms	85112 KB	Output is correct
93	Correct	5011 ms	11516 KB	Output is correct
94	Correct	5027 ms	44152 KB	Output is correct
95	Correct	5001 ms	3308 KB	Output is correct
96	Correct	5001 ms	3436 KB	Output is correct
97	Correct	5014 ms	13120 KB	Output is correct
98	Correct	5008 ms	8144 KB	Output is correct
99	Correct	5008 ms	9008 KB	Output is correct
100	Correct	5040 ms	82724 KB	Output is correct
101	Correct	5021 ms	32360 KB	Output is correct
102	Correct	5025 ms	32336 KB	Output is correct
103	Correct	5037 ms	68280 KB	Output is correct
104	Correct	5045 ms	62976 KB	Output is correct
105	Correct	5005 ms	7048 KB	Output is correct
106	Correct	5061 ms	63068 KB	Output is correct
107	Correct	5021 ms	18992 KB	Output is correct
108	Correct	5009 ms	11300 KB	Output is correct
109	Correct	5002 ms	4716 KB	Output is correct
110	Correct	5005 ms	6380 KB	Output is correct
111	Correct	5014 ms	11636 KB	Output is correct
112	Correct	5036 ms	89348 KB	Output is correct
113	Correct	5067 ms	90672 KB	Output is correct
114	Correct	5045 ms	11896 KB	Output is correct
115	Correct	5036 ms	36344 KB	Output is correct
116	Correct	5063 ms	83564 KB	Output is correct
117	Correct	5038 ms	66704 KB	Output is correct
118	Correct	5069 ms	55060 KB	Output is correct
119	Correct	5042 ms	67636 KB	Output is correct
120	Correct	5022 ms	38068 KB	Output is correct

답안 #379947

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