Submission #805727

#	Time	Username	Problem	Language	Result	Execution time	Memory
805727		YesPy	Cheap flights (LMIO18_pigus_skrydziai)	C++17	100 / 100	938 ms	155684 KiB

pigus_skrydziai

#include <bits/stdc++.h>

#define ff first
#define ss second
#define tcT template<class T
#define fastio ios::sync_with_stdio(false);cin.tie(nullptr);
#define ln '\n'
#define nwln cout<<ln;

using namespace std;

tcT> using vr = vector<T>;
using pi = pair<int, int>;
using vi = vr<int>;
using vpi = vr<pi>;
using ll = long long;
using oo = bool;

#define maxs(i, j) (i = max(i, j))
#define fri(i,a,b) for(int i=(a); i<(b); ++i)
#define each(x, a) for(auto& x: a)

#define sz(x) int((x).size())
#define phb push_back
#define eb emplace_back

const int MX = (int) 3e5+3;
ll N, M, ans;
oo used[MX];
set<int> orz[MX];
vpi adj[MX];

inline void dfs(int u) {
	used[u] = true;
	ll res = 0, xam = 0, U = 0, idx = 0;

	map<int, int> cur;

	each(x, adj[u]) {
		cur[x.ff] = idx++;
		res += x.ss;
		if(xam < x.ss) U = x.ff, xam = x.ss;
	}

	maxs(ans, res);
	// idk if this "if" is necessary
	if(!used[U]) {
		each(x, adj[U]) {
			if(!orz[u].count(x.ff)) continue;
			
			if(cur[x.ff] >= sz(adj[u])) {
				cout<<"why?"<<ln;
				exit(0);
			}

			maxs(ans, xam + x.ss + adj[u][cur[x.ff]].ss);
		}
	}

	each(x, adj[u]) {
		if(!used[x.ff]) dfs(x.ff);
	}
}

int main()
{
	fastio
	cin>>N>>M;

	while(M--) {
		int u, v, w;
		cin>>u>>v>>w;
		adj[u].eb(v, w);
		adj[v].eb(u, w);
		orz[u].insert(v);
		orz[v].insert(u);
	}

	fri(i,1,N+1) {
		if(used[i]) continue;
		dfs(i);
	}

	cout<<ans<<ln;

	return 0;
}

/*
Wow, beautiful trick
Two possible types: star or triangle
Stars are easy, bottleneck are the triangles

What I do is, if I'm on node v then between all its edges I choose the
greatest one and try to match the rest... it can be proved it's correct

Suppose the answer is not correct and let the max-weight triangle be
p, q -> a
q, r -> b
r, p -> c

Then, we're assuming there exists
p, P -> greater than c, a but less than b
q, Q -> greater than a, b but less than c
r, R -> greater than b, c but less than a

Contradiction! We're done :D
*/

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