Submission #1139661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139661		sashaaaa	Cheap flights (LMIO18_pigus_skrydziai)	C++20	16 / 100	1109 ms	140244 KiB

pigus_skrydziai

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

const int NMAX = 3e5 + 5;

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

    friend bool operator < (muchie A, muchie B)
    {
        return A.p > B.p;
    }
};

vector <set<int>> adj;
map<pair <int, int>, long long> cost;
bitset <NMAX> visited;
int parent[NMAX];

void dfs(int nod, int p, long long & ans)
{
    visited[nod] = true;
    parent[nod] = p;

    for(int i : adj[nod])
    {
        if(visited[i] == true && parent[parent[nod]] == i)
        {
            ans = max(ans, 1ll * cost[ {nod, i}] + cost[ {i, p}] + cost[ {p, nod}]);
        }
        if(visited[i] == false)
        {
            dfs(i, nod, ans);
        }
    }
}

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);
    adj.resize(N + 1);

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

        adj[muchii[i].a].insert(muchii[i].b);
        adj[muchii[i].b].insert(muchii[i].a);
        cost[{muchii[i].a, muchii[i].b}] = muchii[i].p;
        cost[{muchii[i].b, muchii[i].a}] = muchii[i].p;
    }

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

    long long ans = 0;
    for(int i = 1; i <= N; i ++)
    {
        ans = max(ans, sum[i]);
    }

    for(int i = 1; i <= N; i ++)
    {
        if(visited[i] == false)
        {
            dfs(i, 0, ans);
        }
    }

    cout << ans << '\n';

    return 0;
}

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