Submission #498904

#	Time	Username	Problem	Language	Result	Execution time	Memory
498904		Kipras	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	2482 ms	85200 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