oj.uz

Submission #751837

# Submission time Handle Problem Language Result Execution time Memory
751837 2023-06-01T15:04:11 Z Kihihihi Robot (JOI21_ho_t4) C++17
100 / 100
 1328 ms 94068 KB 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

struct edge
{
    long long to, p;
};

long long n;
map<long long, vector<edge>> g[100000];
map<long long, long long> sume[100000], dist[100000];

void solve()
{
    long long m;
    cin >> n >> m;
    for (long long i = 0; i < m; i++)
    {
        long long a, b, c, p;
        cin >> a >> b >> c >> p;
        a--; b--;
        g[a][c].push_back({ b, p });
        g[b][c].push_back({ a, p });
    }
    for (long long v = 0; v < n; v++)
    {
        dist[v][0] = INF;
        for (auto& i : g[v])
        {
            for (auto& j : i.second)
            {
                dist[j.to][i.first] = INF;
                sume[v][i.first] += j.p;
            }
        }
    }

    dist[0][0] = 0;
    set<tuple<long long, long long, long long>> q = { { 0, 0, 0 } };
    while (q.size())
    {
        auto [d, v, pc] = *q.begin();
        q.erase(q.begin());

        if (pc != 0)
        {
            for (auto& i : g[v][pc])
            {
                long long add = sume[v][pc] - i.p;
                if (d + add < dist[i.to][0])
                {
                    q.erase({ dist[i.to][0], i.to, 0 });
                    dist[i.to][0] = d + add;
                    q.insert({ dist[i.to][0], i.to, 0 });
                }
            }
            continue;
        }

        for (auto& [col, adj] : g[v])
        {
            for (auto& i : adj)
            {
                long long add = min(i.p, sume[v][col] - i.p);
                if (d + add < dist[i.to][0])
                {
                    q.erase({ dist[i.to][0], i.to, 0 });
                    dist[i.to][0] = d + add;
                    q.insert({ dist[i.to][0], i.to, 0 });
                }

                if (d < dist[i.to][col])
                {
                    q.erase({ dist[i.to][col], i.to, col });
                    dist[i.to][col] = d;
                    q.insert({ dist[i.to][col], i.to, col });
                }
            }
        }
    }
    cout << (dist[n - 1][0] == INF ? -1 : dist[n - 1][0]) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 15 ms 15060 KB Output is correct
10 Correct 12 ms 15036 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 11 ms 14804 KB Output is correct
13 Correct 9 ms 14804 KB Output is correct
14 Correct 10 ms 14804 KB Output is correct
15 Correct 9 ms 14680 KB Output is correct
16 Correct 10 ms 14776 KB Output is correct
17 Correct 9 ms 14804 KB Output is correct
18 Correct 10 ms 14804 KB Output is correct
19 Correct 10 ms 14676 KB Output is correct
20 Correct 10 ms 14676 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 35276 KB Output is correct
2 Correct 89 ms 25420 KB Output is correct
3 Correct 227 ms 30452 KB Output is correct
4 Correct 170 ms 28804 KB Output is correct
5 Correct 1205 ms 89024 KB Output is correct
6 Correct 935 ms 76484 KB Output is correct
7 Correct 400 ms 62956 KB Output is correct
8 Correct 433 ms 52016 KB Output is correct
9 Correct 497 ms 52184 KB Output is correct
10 Correct 443 ms 51740 KB Output is correct
11 Correct 156 ms 40092 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 15 ms 15060 KB Output is correct
10 Correct 12 ms 15036 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 11 ms 14804 KB Output is correct
13 Correct 9 ms 14804 KB Output is correct
14 Correct 10 ms 14804 KB Output is correct
15 Correct 9 ms 14680 KB Output is correct
16 Correct 10 ms 14776 KB Output is correct
17 Correct 9 ms 14804 KB Output is correct
18 Correct 10 ms 14804 KB Output is correct
19 Correct 10 ms 14676 KB Output is correct
20 Correct 10 ms 14676 KB Output is correct
21 Correct 221 ms 35276 KB Output is correct
22 Correct 89 ms 25420 KB Output is correct
23 Correct 227 ms 30452 KB Output is correct
24 Correct 170 ms 28804 KB Output is correct
25 Correct 1205 ms 89024 KB Output is correct
26 Correct 935 ms 76484 KB Output is correct
27 Correct 400 ms 62956 KB Output is correct
28 Correct 433 ms 52016 KB Output is correct
29 Correct 497 ms 52184 KB Output is correct
30 Correct 443 ms 51740 KB Output is correct
31 Correct 156 ms 40092 KB Output is correct
32 Correct 143 ms 27136 KB Output is correct
33 Correct 242 ms 29912 KB Output is correct
34 Correct 522 ms 52976 KB Output is correct
35 Correct 346 ms 44336 KB Output is correct
36 Correct 392 ms 54336 KB Output is correct
37 Correct 493 ms 58776 KB Output is correct
38 Correct 494 ms 66612 KB Output is correct
39 Correct 148 ms 30152 KB Output is correct
40 Correct 487 ms 57456 KB Output is correct
41 Correct 526 ms 57736 KB Output is correct
42 Correct 581 ms 69024 KB Output is correct
43 Correct 267 ms 40288 KB Output is correct
44 Correct 468 ms 43100 KB Output is correct
45 Correct 396 ms 52940 KB Output is correct
46 Correct 325 ms 53252 KB Output is correct
47 Correct 405 ms 58556 KB Output is correct
48 Correct 1328 ms 94068 KB Output is correct