oj.uz

Submission #1046384

# Submission time Handle Problem Language Result Execution time Memory
1046384 2024-08-06T13:45:19 Z xnqs Cheap flights (LMIO18_pigus_skrydziai) C++17
16 / 100
 127 ms 23292 KB 
#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;

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(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
	std::sort(edges.begin(),edges.end());
	for (int i = 1; i <= gs; i++) {
		std::sort(adj_list[i].begin(),adj_list[i].end(),std::greater<std::pair<int,int>>());
		if (adj_list[i].size()>=2) {
			auto [a, wa] = adj_list[i][0];
			auto [b, wb] = adj_list[i][1];

			auto it = std::lower_bound(edges.begin(),edges.end(),std::tuple<int,int,int>(std::min(a,b),std::max(a,b),0));
			if (it!=edges.end()&&std::get<0>(*it)==std::min(a,b)&&std::get<1>(*it)==std::max(a,b)) {
				ans = std::max(ans, (int64_t)wa + wb + std::get<2>(*it));
			}
		}
	}
 
	std::cout << ans << "\n";
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19464 KB Output is correct
2 Correct 127 ms 23292 KB Output is correct
3 Correct 31 ms 6928 KB Output is correct
4 Correct 71 ms 13776 KB Output is correct
5 Correct 110 ms 21248 KB Output is correct
6 Correct 17 ms 3852 KB Output is correct
7 Correct 58 ms 17520 KB Output is correct
8 Correct 74 ms 21968 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 17 ms 3852 KB Output is correct
11 Correct 61 ms 18668 KB Output is correct
12 Correct 44 ms 7336 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 29 ms 3972 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19464 KB Output is correct
2 Correct 127 ms 23292 KB Output is correct
3 Correct 31 ms 6928 KB Output is correct
4 Correct 71 ms 13776 KB Output is correct
5 Correct 110 ms 21248 KB Output is correct
6 Correct 17 ms 3852 KB Output is correct
7 Correct 58 ms 17520 KB Output is correct
8 Correct 74 ms 21968 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 17 ms 3852 KB Output is correct
11 Correct 61 ms 18668 KB Output is correct
12 Correct 44 ms 7336 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 29 ms 3972 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 4 ms 1116 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 0 ms 348 KB Output isn't correct
26 Halted 0 ms 0 KB -