Submission #1122622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122622		ardadut	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	1185 ms	84056 KiB

pigus_skrydziai

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/


ll n,m,ans = 0;
vector<ll> profit;
vector<vector<pair<ll,ll>>> adj;
vector<bool> vis;
map<pair<ll,ll>,ll> mapp;

inline bool comp(pair<ll,ll> pair1, pair<ll,ll> pair2){
    return pair1.second > pair2.second;
}

inline void solve(){

    cin >> n >> m;
    adj.resize(n+1);
    vis.resize(n+1,0);
    profit.resize(n+1,0);

    while(m--){
        ll a,b,c;
        cin >> a >> b >> c;
        profit[a] += c;
        profit[b] += c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
        mapp[{a,b}] = c;
        mapp[{b,a}] = c;
    }

    for(ll i = 1 ; i <= n ; i++){
        ans = max(ans,profit[i]);
        sort(adj[i].begin(), adj[i].end(), comp);
    }

    for(ll i = 1 ; i <= n ; i++){
        if(adj[i].size() < 2) continue;
        if(mapp[{adj[i][0].first,adj[i][1].first}] > 0){
            ans = max(ans,adj[i][0].second + adj[i][1].second + mapp[{adj[i][0].first,adj[i][1].first}]);
        }
    }

    cout << ans << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

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