Submission #1239143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239143		asdfghqwert	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	835 ms	83856 KiB

pigus_skrydziai

//#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC optimize("O3,Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define int long long int
typedef int ll;
using namespace std;
struct edge{
    int v , w;
};
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , m , ans = 0;cin >> n >> m;
    vector<vector<edge>> g(n + 1);
    map<pair<int , int> , int> mp;
    for(int i = 1 ; i <= m ; i++){
        int u , v , w;cin >> u >> v >> w;
        mp[{u,v}] = w;
        mp[{v,u}] = w;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    for(int u = 1 ; u <= n ;u++){
        int tans = 0;
        if(g[u].size() == 0)continue;
        if(g[u].size() == 1)ans = max(ans , g[u][0].w);
        int mxidx = 0 , mxval = -1e9, mx2idx = 0, mx2val = -1e9;
        for(int i = 0 ; i < g[u].size() ; i++){
            tans += g[u][i].w;
            if(mxval < g[u][i].w){mxval = g[u][i].w ; mxidx = g[u][i].v;}
        } 
        if(mxidx == 0)mx2idx = 1;
        for(int i = 0 ; i < g[u].size() ; i++){
            if(g[u][i].v == mxidx)continue;
            if(mx2val < g[u][i].w){mx2val = g[u][i].w ; mx2idx = g[u][i].v;}
        } 
        if(mp.count({mxidx , mx2idx}))tans = max(tans , mxval + mx2val + mp[{mxidx , mx2idx}]);
        ans = max(ans , tans);
    }cout << ans;

}

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