제출 #1169428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169428		Ignut	Cheap flights (LMIO18_pigus_skrydziai)	C++20	37 / 100	318 ms	77088 KiB

pigus_skrydziai

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const bool DEBUG = false;

const int N = 7e5 + 123;

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

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

void Solve() {
    int mmm, n; cin >> mmm >> n;
    int a[n], b[n], c[n];
    for (int i = 0; i <= 2 * n; i ++) sun[i] = 0;
    mpc.clear();
    for (int 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 (int i = 1; i <= 2 * n; i ++) res = max(res, sun[i]);
    for (int i = 0; i <= 2 * n; i ++) b1[i] = b2[i] = {0, 0};
    for (int i = 0; i < n; i ++) {
        pair<ll, int> 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 (int i = 1; i <= 2 * n; 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);

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

/*
*/

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