답안 #1046354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046354	2024-08-06T13:24:41 Z	xnqs	Cheap flights (LMIO18_pigus_skrydziai)	C++17	28 / 100	1696 ms	262144 KB

pigus_skrydziai

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>
#include <unordered_map> 

int gs, edg;
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::tuple<int,int,int>> edges;
std::unordered_map<int,int> umap[500005];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> gs >> edg;
	adj_list.resize(gs+1);
 
	for (int i = 0, a, b, c; i < edg; i++) {
		std::cin >> a >> b >> c;
		adj_list[a].emplace_back(b,c);
		adj_list[b].emplace_back(a,c);
		edges.emplace_back(a,b,c);

		umap[std::min(a,b)][std::max(a,b)] = c;
	}
 
	// try all star graphs
	int64_t ans = 0;
	for (int i = 1; i <= gs; i++) {
		int64_t cand = 0;
		for (const auto& [j, w] : adj_list[i]) {
			cand += w;
		}
		ans = std::max(ans,cand);
	}
 
	// try all "triangle" cycles
	for (const auto& [a, b, c] : edges) {
		int x = a;
		int y = b;
		
		if (adj_list[x].size()>adj_list[y].size()) {
			std::swap(x,y);
		}

		for (const auto& [i, w] : adj_list[x]) {
			if (umap[std::min(y,i)][std::max(y,i)]!=0) {
				ans = std::max(ans,(int64_t)c+w+umap[std::min(y,i)][std::max(y,i)]);
			}
		}
	}
 
	std::cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	27736 KB	Output is correct
2	Correct	5 ms	27740 KB	Output is correct
3	Correct	4 ms	27740 KB	Output is correct
4	Correct	4 ms	27852 KB	Output is correct
5	Correct	5 ms	27740 KB	Output is correct
6	Correct	42 ms	29336 KB	Output is correct
7	Correct	5 ms	27740 KB	Output is correct
8	Correct	4 ms	27740 KB	Output is correct
9	Correct	5 ms	27740 KB	Output is correct
10	Correct	5 ms	27740 KB	Output is correct
11	Correct	5 ms	27996 KB	Output is correct
12	Correct	5 ms	27740 KB	Output is correct
13	Correct	5 ms	27740 KB	Output is correct
14	Correct	4 ms	27740 KB	Output is correct
15	Correct	4 ms	27784 KB	Output is correct
16	Correct	5 ms	27856 KB	Output is correct
17	Correct	5 ms	27736 KB	Output is correct
18	Correct	5 ms	27996 KB	Output is correct
19	Correct	6 ms	28508 KB	Output is correct
20	Correct	5 ms	27828 KB	Output is correct
21	Correct	5 ms	27736 KB	Output is correct

Subtask #2
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	27736 KB	Output is correct
2	Correct	5 ms	27740 KB	Output is correct
3	Correct	4 ms	27740 KB	Output is correct
4	Correct	4 ms	27852 KB	Output is correct
5	Correct	5 ms	27740 KB	Output is correct
6	Correct	42 ms	29336 KB	Output is correct
7	Correct	5 ms	27740 KB	Output is correct
8	Correct	4 ms	27740 KB	Output is correct
9	Correct	5 ms	27740 KB	Output is correct
10	Correct	5 ms	27740 KB	Output is correct
11	Correct	5 ms	27996 KB	Output is correct
12	Correct	5 ms	27740 KB	Output is correct
13	Correct	5 ms	27740 KB	Output is correct
14	Correct	4 ms	27740 KB	Output is correct
15	Correct	4 ms	27784 KB	Output is correct
16	Correct	5 ms	27856 KB	Output is correct
17	Correct	5 ms	27736 KB	Output is correct
18	Correct	5 ms	27996 KB	Output is correct
19	Correct	6 ms	28508 KB	Output is correct
20	Correct	5 ms	27828 KB	Output is correct
21	Correct	5 ms	27736 KB	Output is correct
22	Runtime error	1696 ms	262144 KB	Execution killed with signal 9
23	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	182 ms	79864 KB	Output is correct
2	Correct	314 ms	103932 KB	Output is correct
3	Correct	75 ms	52608 KB	Output is correct
4	Correct	213 ms	77316 KB	Output is correct
5	Correct	368 ms	93940 KB	Output is correct
6	Correct	601 ms	36612 KB	Output is correct
7	Correct	102 ms	94172 KB	Output is correct
8	Correct	103 ms	101372 KB	Output is correct
9	Correct	8 ms	35164 KB	Output is correct
10	Correct	588 ms	36660 KB	Output is correct
11	Correct	58 ms	56288 KB	Output is correct
12	Correct	597 ms	49916 KB	Output is correct
13	Correct	5 ms	27736 KB	Output is correct
14	Correct	973 ms	108088 KB	Output is correct

Subtask #4
0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	182 ms	79864 KB	Output is correct
2	Correct	314 ms	103932 KB	Output is correct
3	Correct	75 ms	52608 KB	Output is correct
4	Correct	213 ms	77316 KB	Output is correct
5	Correct	368 ms	93940 KB	Output is correct
6	Correct	601 ms	36612 KB	Output is correct
7	Correct	102 ms	94172 KB	Output is correct
8	Correct	103 ms	101372 KB	Output is correct
9	Correct	8 ms	35164 KB	Output is correct
10	Correct	588 ms	36660 KB	Output is correct
11	Correct	58 ms	56288 KB	Output is correct
12	Correct	597 ms	49916 KB	Output is correct
13	Correct	5 ms	27736 KB	Output is correct
14	Correct	973 ms	108088 KB	Output is correct
15	Correct	5 ms	27736 KB	Output is correct
16	Correct	5 ms	27740 KB	Output is correct
17	Correct	4 ms	27740 KB	Output is correct
18	Correct	4 ms	27852 KB	Output is correct
19	Correct	5 ms	27740 KB	Output is correct
20	Correct	42 ms	29336 KB	Output is correct
21	Correct	5 ms	27740 KB	Output is correct
22	Correct	4 ms	27740 KB	Output is correct
23	Correct	5 ms	27740 KB	Output is correct
24	Correct	5 ms	27740 KB	Output is correct
25	Correct	5 ms	27996 KB	Output is correct
26	Correct	5 ms	27740 KB	Output is correct
27	Correct	5 ms	27740 KB	Output is correct
28	Correct	4 ms	27740 KB	Output is correct
29	Correct	4 ms	27784 KB	Output is correct
30	Correct	5 ms	27856 KB	Output is correct
31	Correct	5 ms	27736 KB	Output is correct
32	Correct	5 ms	27996 KB	Output is correct
33	Correct	6 ms	28508 KB	Output is correct
34	Correct	5 ms	27828 KB	Output is correct
35	Correct	5 ms	27736 KB	Output is correct
36	Runtime error	1696 ms	262144 KB	Execution killed with signal 9
37	Halted	0 ms	0 KB	-

답안 #1046354

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 25.0

Subtask #3 16.0 / 16.0

Subtask #4 0 / 47.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 25.0

Subtask #3
16.0 / 16.0

Subtask #4
0 / 47.0