Submission #973377

#	Time	Username	Problem	Language	Result	Execution time	Memory
973377		AtabayRajabli	Cheap flights (LMIO18_pigus_skrydziai)	C++17	0 / 100	199 ms	52196 KiB

pigus_skrydziai

#include <bits/stdc++.h>
#define int ll
#define all(v) v.begin(), v.end()
 
// author : a1abay
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
const int sz = 3e5 + 5;
const int inf = 1e9 + 7;
 
int n, m, ans, u, v, w;
set<array<int, 2>> g[sz];
int used[sz];

void dfs(int v, int p, int pw)
{
    used[v] = 1;
    for(auto i : g[v])
    {
        if(used[i[0]])
        {
            if(i[0] != p)
            {
                auto fnd = g[p].lower_bound({i[0], 0});
                if(fnd != g[p].end()) ans = max(ans, i[1] + pw + (*fnd)[1]);
            }
            continue;
        }
        if(i[0] != p)
        {
            auto fnd = g[p].lower_bound({i[0], 0});
            if(fnd != g[p].end()) ans = max(ans, i[1] + pw + (*fnd)[1]);
        }
        dfs(i[0], v, i[1]);
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        g[u].insert({v, w});
        g[v].insert({u, w});
    }

    for(int i = 1; i <= n; i++)
    {
        int s = 0;
        for(auto j : g[i])
        {
            s += j[1];
        }
        ans = max(ans, s);
    }

    dfs(1, 0, 0);

    cout << ans;
}

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