oj.uz

Submission #973377

# Submission time Handle Problem Language Result Execution time Memory
973377 2024-05-01T21:13:25 Z AtabayRajabli Cheap flights (LMIO18_pigus_skrydziai) C++17
0 / 100
 199 ms 52196 KB 
#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.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 33412 KB Output is correct
2 Incorrect 199 ms 52196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 33412 KB Output is correct
2 Incorrect 199 ms 52196 KB Output isn't correct
3 Halted 0 ms 0 KB -