Submission #1165717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165717		tamyte	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	1338 ms	63196 KiB

pigus_skrydziai

#include <bits/stdc++.h>



using namespace std;
using ll = long long;
map<pair<int, int>, ll> mp;
vector<vector<pair<int, ll>>> mx;

void check(int a, int b, ll w) {
	if (mx[a][0].second < w) {
		mx[a][1] = mx[a][0];
		mx[a][0] = {b, w};
	} else if (mx[a][1].second < w) {
		mx[a][1] = {b, w};
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<ll> c(n);
	mx = vector<vector<pair<int, ll>>>(n, vector<pair<int, ll>>(2, {-1, -1}));
	for (int i = 0; i < m; ++i) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		--a; --b;
		c[a] += w;
		c[b] += w;
		mp[{a, b}] = mp[{b, a}] = w;
		check(a, b, w);
		check(b, a, w);
	}
	ll res = *max_element(begin(c), end(c));
	for (int i = 0; i < n; ++i) {
		int p = mx[i][0].first;
		int q = mx[i][1].first;
		ll sum = 0;
		for (int j = 0; j < 2; ++j) {
			sum += mx[i][j].second;
		}
		if (mp.count({p, q})) {
			sum += mp[{p, q}];
			res = max(res, sum);
		}
	}
	cout << res << endl;
}

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