Submission #791867

#	Time	Username	Problem	Language	Result	Execution time	Memory
791867		Cookie	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	343 ms	66612 KiB

pigus_skrydziai

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ll mxn = 3e5 + 5, base = 972663749;
const ll mod = 911382323, inf = 1e9;
int n, m;
vt<pll>g[mxn + 1], adj[mxn + 1];
ll cost[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    forr(i, 0, m){
        ll u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w}); adj[v].pb({u, w}); cost[u] += w; cost[v] += w;
        g[u].pb({w, v}); g[v].pb({w, u});
    }
    for(int u = 1; u <= n; u++){
        sort(adj[u].begin(), adj[u].end());
        sort(g[u].rbegin(), g[u].rend());
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, cost[i]);
        if(sz(g[i]) < 2)continue;
        int u = g[i][0].se, v = g[i][1].se;
        int id = lower_bound(adj[u].begin(), adj[u].end(), make_pair(v, (ll)-1)) - adj[u].begin();
        if(id != sz(adj[u]) && adj[u][id].fi == v){
            ans = max(ans, g[i][0].fi + g[i][1].fi + adj[u][id].se);
        }
    }
    cout << ans;
    return(0);
}

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