제출 #1240439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240439		rayan_bd	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	1228 ms	113380 KiB

pigus_skrydziai

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

#define ll long long
#define all(x) x.begin(), x.end()

const int mxN = 3e5 + 10;

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


int main(){
/*	freopen("inp.in", "r", stdin);
	freopen("output.out", "w", stdout);
*/

	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(int i = 1; i <= n; ++i){
		sort(all(adj[i]), [&](pair<ll, ll> p1, pair<ll, ll> p2){
			return p1.second > p2.second;
		});
	}

	sort(all(edge), [&](vector<ll> v1, vector<ll> v2){
		return v1[2] > v2[2];
	});

	while(edge.size() > n) edge.pop_back();

	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: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 47 / 47