Submission #1169434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169434		Ignut	Cheap flights (LMIO18_pigus_skrydziai)	C++20	53 / 100	300 ms	56716 KiB

pigus_skrydziai

/* Ignut
date: 18.03.2025
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const bool DEBUG = false;

const ll N = 2e6 + 123;

ll sun[2 * N];
map<pair<ll, ll>, ll> mpc; 

pair<ll, ll> b1[2 * N], b2[2 * N];

void Solve() {
    ll mmm, n; cin >> mmm >> n;
    ll a[n], b[n], c[n];
    for (ll i = 0; i <= mmm; i ++) sun[i] = 0;
    mpc.clear();
    for (ll i = 0; i < n; i ++) {
        cin >> a[i] >> b[i] >> c[i];
        sun[a[i]] += c[i], sun[b[i]] += c[i];
        mpc[{a[i], b[i]}] = c[i];
    }
    ll res = 0;
    for (ll i = 1; i <= mmm; i ++) res = max(res, sun[i]);
    for (ll i = 0; i <= mmm; i ++) b1[i] = b2[i] = {0, 0};
    for (ll i = 0; i < n; i ++) {
        pair<ll, ll> p = {c[i], b[i]};
        if (p > b1[a[i]]) b2[a[i]] = b1[a[i]], b1[a[i]] = p;
        else if (p > b2[a[i]]) b2[a[i]] = p;
        p = {c[i], a[i]};
        if (p > b1[b[i]]) b2[b[i]] = b1[b[i]], b1[b[i]] = p;
        else if (p > b2[b[i]]) b2[b[i]] = p;
    }
    for (ll i = 1; i <= mmm; i ++) {
        if (b2[i].second == 0) continue;
        res = max(res, b1[i].first + b2[i].first + mpc[{min(b1[i].second, b2[i].second), max(b1[i].second, b2[i].second)}]);
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);

    // ll t; cin >> t;
    // while (t --> 0) {
    Solve();
    // }
    return 0;
}

/*
*/

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