Submission #1129135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129135		12345678	Cheap flights (LMIO18_pigus_skrydziai)	C++17	100 / 100	540 ms	59360 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;

#define ll long long

ll n, m, u, v, w, dp[nx], mx;
vector<pair<ll, ll>> d[nx];
map<pair<ll, ll>, ll> mp;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, d[u].push_back({w, v}), d[v].push_back({w, u}), dp[u]+=w, dp[v]+=w, mp[{min(u, v), max(u, v)}]=w;
    for (int i=1; i<=n; i++) 
    {
        mx=max(mx, dp[i]);
        sort(d[i].begin(), d[i].end());
        reverse(d[i].begin(), d[i].end());
        if (d[i].size()>1) 
        {
            ll x=d[i][0].second, y=d[i][1].second;
            if (mp.find({min(x, y), max(x, y)})!=mp.end()) mx=max(mx, d[i][0].first+d[i][1].first+mp[{min(x, y), max(x, y)}]);
        }
    }
    cout<<mx;
}

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