oj.uz

Submission #973375

# Submission time Handle Problem Language Result Execution time Memory
973375 2024-05-01T21:10:54 Z Captain_Georgia Cheap flights (LMIO18_pigus_skrydziai) C++17
0 / 100
 318 ms 46032 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 32036 KB Output is correct
2 Incorrect 318 ms 46032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 32036 KB Output is correct
2 Incorrect 318 ms 46032 KB Output isn't correct
3 Halted 0 ms 0 KB -