Submission #1139654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139654		sashaaaa	Cheap flights (LMIO18_pigus_skrydziai)	C++20	28 / 100	3096 ms	94520 KiB

pigus_skrydziai

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 3e5 + 5;

struct muchie
{
    int a, b;
    long long p;

    friend bool operator < (muchie A, muchie B)
    {
        return A.p > B.p;
    }
};
//
struct PairHash
{
    size_t operator()(const pair<int,int> &pr) const
    {
        auto h1 = std :: hash <long long>()((long long) pr.first);
        auto h2 = std :: hash <long long>()((long long) pr.second);
        h1 ^= (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
        return h1;
    }
};
//
int main()
{
    cin.tie(nullptr);
    ios_base :: sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<muchie> muchii(M);
    vector<long long> sum(N + 1, 0ll);

    for(int i = 0; i < M; i ++)
    {
        cin >> muchii[i].a >> muchii[i].b >> muchii[i].p;
    }

    for(auto & i : muchii)
    {
        sum[i.a] += i.p;
        sum[i.b] += i.p;
    }

    long long best = 0;
    for(int v = 1; v <= N; v++)
    {
        if(sum[v] > best)
        {
            best = sum[v];
        }
    }

    unordered_map <pair<int,int>, long long, PairHash> mp;
    mp.reserve(M * 2);

    for(auto & i : muchii)
    {
        int x = i.a, y = i.b;

        if(x > y) swap(x, y);

        mp[{x, y}] = i.p;
    }

    vector <unordered_set<int>> adj(N + 1);

    sort(muchii.begin(), muchii.end());

    long long best1 = 0;

    for(auto & i : muchii)
    {
        int x = i.a, y = i.b;
        long long cost1 = i.p;

        if(adj[x].size() > adj[y].size()) swap(x, y);

        for(int e : adj[x])
        {
            if(adj[y].count(e))
            {
                int xx = x, yy = e;
                if(xx > yy) swap(xx, yy);
                long long cost2 = mp[{xx, yy}];

                xx = y, yy = e;
                if(xx > yy) swap(xx, yy);
                long long cost3 = mp[{xx, yy}];

                long long suma = cost1 + cost2 + cost3;

                best1 = max(best1, suma);
            }
        }

        adj[x].insert(y);
        adj[y].insert(x);
    }

    long long ans = max(best, best1);

    cout << ans << '\n';

    return 0;
}

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