Submission #973375

#	Time	Username	Problem	Language	Result	Execution time	Memory
973375		Captain_Georgia	Cheap flights (LMIO18_pigus_skrydziai)	C++17	0 / 100	318 ms	46032 KiB

pigus_skrydziai

#include <bits/stdc++.h>
using namespace std;
 
    
int TIME = clock();

#define file \
            freopen("in.txt" , "r" , stdin); \
            freopen("out.txt" , "w" , stdout);
 
typedef long long ll;

void test_case () {
    int n , m;
    cin >> n >> m;
    set<pair<int , int>> g[n + 1];
    vector<ll> sum(n + 1 , 0);
    for (int i = 0;i < m;i ++) {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].insert({v , w});
        g[v].insert({u , w});
        sum[u] += w;
        sum[v] += w;
    }
    vector<int> used(n + 1 , 0);
    ll res = 0;
    function<void(int , int , int)> dfs = [&](int si, int pi, int val) -> void {
        used[si] = 1;
        for (auto i : g[si]) {
            if (i.first == pi) {
                continue;
            }
            auto it = g[pi].lower_bound({i.first , 0});
            if (it != g[pi].end()) {
                res = max(res , (ll)(*it).second + i.second + val);
            }
            if (used[i.first] == 0) {
                dfs (i.first , si , i.second);
            }
        }
    };
    dfs (1 , 0 , 0);
    for (int i = 1;i <= n;i ++) {
        res = max(res , sum[i]);
    }
    cout << res << "\n";
}
 
int32_t main () {
 
    ///    file
    
 
    int t = 1;
    // cin >> t;
 
    while (t --) {
        test_case();
    }
 
    cerr << "\nTime elapsed: " << (clock() - TIME) * 1000.0 / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

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