Submission #198470

#	Time	Username	Problem	Language	Result	Execution time	Memory
198470		oolimry	Cheap flights (LMIO18_pigus_skrydziai)	C++14	16 / 100	1549 ms	101660 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long,long long> ii; 
static vector<ii> adj[500005];
static vector<ii> tree[500005];
map<ii, long long> thonk;
static long long p[500005];

long long findSet(long long u){
	if(p[u] == u) return u;
	else{
		p[u] = findSet(p[u]);
		return p[u];
	}
}
 
bool unionSet(long long u, long long v){
	u = findSet(u);
	v = findSet(v);
	if(u == v) return false;
	p[u] = v;
	return true;
}


struct edge{
	long long u;
	long long v;
	long long w;
};

bool comp(edge a, edge b){
	return a.w > b.w;
}
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n, m; cin >> n >> m;
	edge edges[m];
	
	for(long long i = 0;i < n;i++) p[i] = i;

	for(long long i = 0;i < m;i++){
		long long u, v; long long w;
		cin >> u >> v >> w; u--; v--;
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
		edges[i] = {u,v,w};
		thonk[ii(u,v)] = w;
		thonk[ii(v,u)] = w;
	}
	
	long long ans = 0;
	
	for(long long i = 0;i < n;i++){
		long long acc = 0;
		for(ii v : adj[i]) acc += v.second;
		ans = max(ans, acc);
	}
	
	sort(edges,edges+m,comp);
	
	for(edge e : edges){
		if(unionSet(e.u, e.v)){
			tree[e.u].push_back(ii(e.v,e.w));
			tree[e.v].push_back(ii(e.u,e.w));
		}
	}
	
	for(long long i = 0;i < n;i++){
		if(tree[i].size() == 2){
			ii u = tree[i][0];
			ii v = tree[i][1];
			if(thonk.find(ii(u.first,v.first)) != thonk.end()){
				ans = max(ans, u.second + v.second + thonk[ii(u.first,v.first)]);
			}
		}
	}
	
	cout << ans;
}

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