oj.uz

Submission #1046283

# Submission time Handle Problem Language Result Execution time Memory
1046283 2024-08-06T12:27:50 Z xnqs Cheap flights (LMIO18_pigus_skrydziai) C++17
12 / 100
 3000 ms 47444 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>

int gs, edg;
std::vector<std::set<std::pair<int,int>>> adj_list;

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(b,c);
		adj_list[b].emplace(a,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
#if 1
	for (int i = 1; i <= gs; i++) {
		for (const auto& [j, wj] : adj_list[i]) {
			if (j<i) {
				continue;
			}
			for (const auto& [k, wk] : adj_list[j]) {
				if (k==i) {
					continue;
				}

				auto it = adj_list[k].lower_bound(std::pair<int,int>(i,0));
				if (it!=adj_list[k].end()&&it->first==i) {
					//std::cout << i << " " << j << " " << k << "\n";
					//std::cout << wj << " " << wk << " " << it->second << "\n";
					ans = std::max(ans, static_cast<int64_t>(wj)+wk+it->second);
				}
			}
		}
	}
#endif

	std::cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 67 ms 2140 KB Output is correct
7 Correct 0 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 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 67 ms 2140 KB Output is correct
7 Correct 0 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 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Execution timed out 3026 ms 47444 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28508 KB Output is correct
2 Correct 137 ms 42576 KB Output is correct
3 Correct 27 ms 14428 KB Output is correct
4 Correct 63 ms 28056 KB Output is correct
5 Correct 233 ms 37968 KB Output is correct
6 Correct 1836 ms 12176 KB Output is correct
7 Correct 55 ms 40272 KB Output is correct
8 Correct 64 ms 47188 KB Output is correct
9 Correct 3 ms 14428 KB Output is correct
10 Correct 1834 ms 13416 KB Output is correct
11 Correct 95 ms 38480 KB Output is correct
12 Execution timed out 3065 ms 26292 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28508 KB Output is correct
2 Correct 137 ms 42576 KB Output is correct
3 Correct 27 ms 14428 KB Output is correct
4 Correct 63 ms 28056 KB Output is correct
5 Correct 233 ms 37968 KB Output is correct
6 Correct 1836 ms 12176 KB Output is correct
7 Correct 55 ms 40272 KB Output is correct
8 Correct 64 ms 47188 KB Output is correct
9 Correct 3 ms 14428 KB Output is correct
10 Correct 1834 ms 13416 KB Output is correct
11 Correct 95 ms 38480 KB Output is correct
12 Execution timed out 3065 ms 26292 KB Time limit exceeded
13 Halted 0 ms 0 KB -