Submission #382247

#	Time	Username	Problem	Language	Result	Execution time	Memory
382247		MohamedAhmed04	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	1502 ms	81644 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 3e5 + 10 ;

long long sum[MAX] ;
int n , m ;

vector< vector< pair<int , int> > >adj(MAX) ;

map< pair<int , int> , int>mp ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	long long ans = 0 ; 
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y , z ;
		cin>>x>>y>>z ;
		sum[x] += z , sum[y] += z ;
		mp[{x , y}] = mp[{y , x}] = z ;
		adj[x].emplace_back(z , y) ;
		adj[y].emplace_back(z , x) ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		ans = max(ans , sum[i]) ;
		sort(adj[i].begin() , adj[i].end()) ;
		reverse(adj[i].begin() , adj[i].end()) ;
		if(adj[i].size() > 1)
		{
			long long x = adj[i][0].first , y = adj[i][1].first ;
			int a = adj[i][0].second , b = adj[i][1].second ;
			ans = max(ans , x + y + mp[{a , b}]) ;
		}
	}
	return cout<<ans<<"\n" , 0 ;
}		

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