oj.uz

Submission #634727

# Submission time Handle Problem Language Result Execution time Memory
634727 2022-08-24T18:13:30 Z mrkhan2000 Cheap flights (LMIO18_pigus_skrydziai) C++17
0 / 100
 1991 ms 262144 KB 
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

const int mxN = (int)3e5;
set<int> adj[mxN];
map<pair<int,int>, ll> w;

void solve() {
	int N, E; cin >> N >> E;
	vector<ll> ws(N);
	for(int i = 0; i < E; i++) {
		int U, V, P;
		cin >> U >> V >> P;
		--U, --V;
		ws[U] += P;
		ws[V] += P;
		adj[U].insert(V);
		adj[V].insert(U);
		w[{U,V}] = P;
		w[{V,U}] = P;
	}
	ll ans = *max_element(ws.begin(), ws.end());
	set<set<int>> cycles;
	for(int i = 0; i < N; i++) {
		set<int> visited;
		for(int v : adj[i]) {
			for(int n : visited) {
				if(adj[v].find(n) != adj[v].end()) {
					set<int> cycle = {i, v, n};
					if(cycles.find(cycle) == cycles.end()) {
						ans = max(ans, w[{i,v}] + w[{v,n}] + w[{i,n}]);
						cycles.insert(cycle);
					}
				}
			}
			visited.insert(v);
		}
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int test_cases = 1;
	// cin >> test_cases;
	for(int test_case = 1; test_case <= test_cases; test_case++) {
		// cout << "Case #" << test_case << ": ";
		solve();
	}
	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14312 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14304 KB Output is correct
6 Runtime error 1991 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14312 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14304 KB Output is correct
6 Runtime error 1991 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 51928 KB Output is correct
2 Correct 636 ms 86984 KB Output is correct
3 Correct 187 ms 38352 KB Output is correct
4 Correct 394 ms 61104 KB Output is correct
5 Correct 1078 ms 86060 KB Output is correct
6 Runtime error 1462 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 51928 KB Output is correct
2 Correct 636 ms 86984 KB Output is correct
3 Correct 187 ms 38352 KB Output is correct
4 Correct 394 ms 61104 KB Output is correct
5 Correct 1078 ms 86060 KB Output is correct
6 Runtime error 1462 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -