oj.uz

Submission #708507

# Submission time Handle Problem Language Result Execution time Memory
708507 2023-03-11T21:33:49 Z finn__ Robot (JOI21_ho_t4) C++17
100 / 100
 618 ms 65956 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 100000;

vector<tuple<size_t, size_t, size_t>> g[N];
map<size_t, size_t> ccost[N], f[N];
size_t d[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m;
    cin >> n >> m;

    for (size_t i = 0; i < m; i++)
    {
        size_t u, v, c, p;
        cin >> u >> v >> c >> p;
        g[u - 1].emplace_back(v - 1, c, p);
        g[v - 1].emplace_back(u - 1, c, p);
        ccost[u - 1][c] += p;
        ccost[v - 1][c] += p;
    }

    auto compare_second = [](tuple<size_t, size_t, size_t> const &a,
                             tuple<size_t, size_t, size_t> const &b)
    { return get<1>(a) > get<1>(b); };

    for (size_t i = 0; i < n; i++)
        sort(g[i].begin(), g[i].end(), compare_second);

    priority_queue<tuple<size_t, size_t, size_t>,
                   vector<tuple<size_t, size_t, size_t>>, decltype(compare_second)>
        q(compare_second);

    fill(d + 1, d + n, SIZE_MAX);
    q.emplace(0, 0, 0);

    while (!q.empty())
    {
        auto const [u, dis, c] = q.top();
        q.pop();

        if ((!c && dis != d[u]) || (c && dis != f[u][c]))
            continue;

        if (c)
        {
            auto it = lower_bound(
                g[u].begin(), g[u].end(), (tuple<size_t, size_t, size_t>){0, c, 0},
                compare_second);
            while (it != g[u].end() && get<1>(*it) == c)
            {
                if (dis + ccost[u][c] - get<2>(*it) < d[get<0>(*it)])
                {
                    d[get<0>(*it)] = dis + ccost[u][c] - get<2>(*it);
                    q.emplace(get<0>(*it), d[get<0>(*it)], 0);
                }
                it++;
            }
            continue;
        }
        for (auto const &[v, ec, p] : g[u])
        {
            if (f[v].find(ec) == f[v].end() || dis < f[v][ec])
            {
                f[v][ec] = dis;
                q.emplace(v, dis, ec);
            }
            if (dis + p < d[v])
            {
                d[v] = dis + p;
                q.emplace(v, d[v], 0);
            }
            if (dis + ccost[u][ec] - p < d[v])
            {
                d[v] = dis + ccost[u][ec] - p;
                q.emplace(v, d[v], 0);
            }
        }
    }

    cout << (d[n - 1] == SIZE_MAX ? -1 : (int64_t)d[n - 1]) << '\n';
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12072 KB Output is correct
3 Correct 9 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12500 KB Output is correct
10 Correct 8 ms 12500 KB Output is correct
11 Correct 7 ms 12372 KB Output is correct
12 Correct 8 ms 12352 KB Output is correct
13 Correct 8 ms 12356 KB Output is correct
14 Correct 9 ms 12428 KB Output is correct
15 Correct 7 ms 12260 KB Output is correct
16 Correct 8 ms 12272 KB Output is correct
17 Correct 7 ms 12244 KB Output is correct
18 Correct 6 ms 12184 KB Output is correct
19 Correct 8 ms 12236 KB Output is correct
20 Correct 9 ms 12244 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 26992 KB Output is correct
2 Correct 57 ms 19400 KB Output is correct
3 Correct 139 ms 27200 KB Output is correct
4 Correct 83 ms 21924 KB Output is correct
5 Correct 618 ms 60284 KB Output is correct
6 Correct 472 ms 56664 KB Output is correct
7 Correct 249 ms 46480 KB Output is correct
8 Correct 295 ms 43120 KB Output is correct
9 Correct 364 ms 43220 KB Output is correct
10 Correct 243 ms 37940 KB Output is correct
11 Correct 95 ms 25904 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12072 KB Output is correct
3 Correct 9 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12500 KB Output is correct
10 Correct 8 ms 12500 KB Output is correct
11 Correct 7 ms 12372 KB Output is correct
12 Correct 8 ms 12352 KB Output is correct
13 Correct 8 ms 12356 KB Output is correct
14 Correct 9 ms 12428 KB Output is correct
15 Correct 7 ms 12260 KB Output is correct
16 Correct 8 ms 12272 KB Output is correct
17 Correct 7 ms 12244 KB Output is correct
18 Correct 6 ms 12184 KB Output is correct
19 Correct 8 ms 12236 KB Output is correct
20 Correct 9 ms 12244 KB Output is correct
21 Correct 135 ms 26992 KB Output is correct
22 Correct 57 ms 19400 KB Output is correct
23 Correct 139 ms 27200 KB Output is correct
24 Correct 83 ms 21924 KB Output is correct
25 Correct 618 ms 60284 KB Output is correct
26 Correct 472 ms 56664 KB Output is correct
27 Correct 249 ms 46480 KB Output is correct
28 Correct 295 ms 43120 KB Output is correct
29 Correct 364 ms 43220 KB Output is correct
30 Correct 243 ms 37940 KB Output is correct
31 Correct 95 ms 25904 KB Output is correct
32 Correct 109 ms 27872 KB Output is correct
33 Correct 126 ms 28760 KB Output is correct
34 Correct 316 ms 42132 KB Output is correct
35 Correct 233 ms 35184 KB Output is correct
36 Correct 243 ms 37760 KB Output is correct
37 Correct 271 ms 41488 KB Output is correct
38 Correct 284 ms 52664 KB Output is correct
39 Correct 146 ms 33576 KB Output is correct
40 Correct 331 ms 44568 KB Output is correct
41 Correct 345 ms 44604 KB Output is correct
42 Correct 390 ms 49620 KB Output is correct
43 Correct 164 ms 30252 KB Output is correct
44 Correct 254 ms 40020 KB Output is correct
45 Correct 238 ms 39764 KB Output is correct
46 Correct 222 ms 38664 KB Output is correct
47 Correct 271 ms 40560 KB Output is correct
48 Correct 606 ms 65956 KB Output is correct