oj.uz

Submission #656931

# Submission time Handle Problem Language Result Execution time Memory
656931 2022-11-08T14:12:42 Z pls33 Cheap flights (LMIO18_pigus_skrydziai) C++17
12 / 100
 3000 ms 27112 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;

template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

const int BUF_SZ = 1 << 15;
inline namespace fast_in
{
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char(FILE *f)
    {
        if (pos == len)
        {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, f);

            if (!len)
            {
                return EOF;
            }
        }

        return buf[pos++];
    }

    int read_int(FILE *f)
    {
        int x;
        char ch;
        int sgn = 1;

        while (!isdigit(ch = next_char(f)))
        {
            if (ch == '-')
            {
                sgn *= -1;
            }
        }

        x = ch - '0';
        while (isdigit(ch = next_char(f)))
        {
            x = x * 10 + (ch - '0');
        }

        return x * sgn;
    }
}

/**
 * @brief gale programos flush_out kviest!!
 */
inline namespace fast_out
{
    char buf[BUF_SZ];
    int pos;

    void flush_out(FILE *f)
    {
        fwrite(buf, 1, pos, f);
        pos = 0;
    }

    void write_char(char c, FILE *f)
    {
        if (pos == BUF_SZ)
        {
            flush_out(f);
        }

        buf[pos++] = c;
    }

    void write_int(int x, FILE *f)
    {
        static char num_buf[100];

        if (x < 0)
        {
            write_char('-', f);
            x *= -1;
        }

        int len = 0;
        for (; x >= 10; x /= 10)
        {
            num_buf[len++] = (char)('0' + (x % 10));
        }

        write_char((char)('0' + x), f);
        while (len)
        {
            write_char(num_buf[--len], f);
        }
        write_char('\n', f);
    }
}
#pragma endregion

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("flight.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int v, e;
    cin >> v >> e;

    vi64 sum(v);
    vvp32 adj(v);

    vector<tuple<int, int, int>> edges(e);
    for (int i = 0; i < e; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;

        a--;
        b--;

        edges[i] = {a, b, w};
        sum[a] += w;
        sum[b] += w;

        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }

    for (int i = 0; i < v; i++)
    {
        sort(adj[i].begin(), adj[i].end());
    }

    int64_t result = *max_element(sum.begin(), sum.end());

    for (auto &edge : edges)
    {
        auto &[a, b, w] = edge;
        for (auto &next : adj[a])
        {
            p32 val = {next.first, 0};
            auto it = lower_bound(adj[b].begin(), adj[b].end(), val);

            if (it == adj[b].end() || it->first != next.first)
            {
                continue;
            }

            int64_t cur = (int64_t)w + it->second + next.second;
            result = max(result, cur);
        }
    }

    cout << result << '\n';

    return 0;
}

Compilation message

pigus_skrydziai.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
pigus_skrydziai.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      |

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 62 ms 1228 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 62 ms 1228 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Execution timed out 3016 ms 25896 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 22992 KB Output is correct
2 Correct 206 ms 27112 KB Output is correct
3 Correct 57 ms 9128 KB Output is correct
4 Correct 129 ms 18172 KB Output is correct
5 Correct 239 ms 24272 KB Output is correct
6 Correct 1363 ms 4948 KB Output is correct
7 Correct 84 ms 23240 KB Output is correct
8 Correct 124 ms 27084 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 1407 ms 5068 KB Output is correct
11 Execution timed out 3078 ms 20412 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 22992 KB Output is correct
2 Correct 206 ms 27112 KB Output is correct
3 Correct 57 ms 9128 KB Output is correct
4 Correct 129 ms 18172 KB Output is correct
5 Correct 239 ms 24272 KB Output is correct
6 Correct 1363 ms 4948 KB Output is correct
7 Correct 84 ms 23240 KB Output is correct
8 Correct 124 ms 27084 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 1407 ms 5068 KB Output is correct
11 Execution timed out 3078 ms 20412 KB Time limit exceeded
12 Halted 0 ms 0 KB -