Submission #499117

#	Time	Username	Problem	Language	Result	Execution time	Memory
499117		Kipras	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	2138 ms	85196 KiB

pigus_skrydziai

#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
 
const ll maxN = (1e5*5)+10;
 
ll n, m;
vector<ll> adj[maxN];
map<pair<ll, ll>, ll> adjFast;
 
int main()
{
 
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
 
    cin>>n>>m;
    for(ll i = 0; i < m; i++){
        ll a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back(b);
        adj[b].push_back(a);
        adjFast[{a, b}]=c;
        adjFast[{b, a}]=c;
    }
 
    ll ans=0;
 
    for(ll i = 1; i <= n; i++){
        ll temp=0;
        for(auto x : adj[i]){
            temp+=adjFast[{i, x}];
        }
        for(ll x = 0; x < (ll)(adj[i].size())-1; x++){
            ll v1=adj[i][x], v2=adj[i][x+1];
            if(adjFast.count({v1, v2})){
                temp=max(temp, adjFast[{i, v1}]+adjFast[{i, v2}]+adjFast[{v1, v2}]);
            }
        }
 
        ans=max(ans, temp);
    }
 
    cout<<ans;
 
    return 0;
}

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