Submission #1238056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238056		i_love_mriti	Cheap flights (LMIO18_pigus_skrydziai)	C++20	28 / 100	3097 ms	113184 KiB

pigus_skrydziai

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN = 3e5 + 100;

vector<pair<ll, ll>> adj[mxN];
vector<vector<ll>> edge;
ll cst[mxN];
unordered_map<ll,ll> mp[mxN];


int main(){

	ll n, m, u, v, w, ans = 0;
	cin >> n >> m;

	for(ll i = 0; i < m; ++i){
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		mp[u][v] = w;
		mp[v][u] = w;
		edge.push_back({u, v, w});
		cst[u] += w, cst[v] += w;
		ans = max({ans, cst[u], cst[v]});
	}

	for(auto it : edge){
		u = it[0], v = it[1], w = it[2];
		if(adj[u].size() > adj[v].size()){
			for(auto it : adj[v]){
				if(mp[u].find(it.first) != mp[u].end()){
					ans = max(ans, w + it.second + mp[u][it.first]);
				}
			}
		}else{
		for(auto it : adj[u]){
				if(mp[v].find(it.first) != mp[v].end()){
					ans = max(ans, w + it.second + mp[v][it.first]);
				}
			}
		}
	}

	cout << ans << "\n";

	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 25
• Subtask 3: 16 / 16
• Subtask 4: 0 / 47