oj.uz

Submission #751828

# Submission time Handle Problem Language Result Execution time Memory
751828 2023-06-01T14:48:15 Z Kihihihi Robot (JOI21_ho_t4) C++17
24 / 100
 1312 ms 92228 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)
        {
            long long del = -INF;
            for (auto& i : g[v][pc])
            {
                if (dist[i.to][0] + i.p == d)
                {
                    del = max(del, i.p);
                }
            }

            for (auto& i : g[v][pc])
            {
                long long add = sume[v][pc] - del - i.p;
                add = max(add, 0ll);
                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][col])
                {
                    q.erase({ dist[i.to][col], i.to, col });
                    dist[i.to][col] = d + add;
                    q.insert({ dist[i.to][col], i.to, col });
                }
                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 });
                }
            }
        }
    }
    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
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14348 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 8 ms 14292 KB Output is correct
7 Correct 12 ms 14552 KB Output is correct
8 Correct 8 ms 14476 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct
10 Correct 13 ms 15060 KB Output is correct
11 Correct 9 ms 14932 KB Output is correct
12 Incorrect 10 ms 14804 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 36408 KB Output is correct
2 Correct 97 ms 25912 KB Output is correct
3 Correct 207 ms 31536 KB Output is correct
4 Correct 139 ms 29636 KB Output is correct
5 Correct 1312 ms 92228 KB Output is correct
6 Correct 931 ms 84072 KB Output is correct
7 Correct 394 ms 66872 KB Output is correct
8 Correct 449 ms 56284 KB Output is correct
9 Correct 447 ms 56228 KB Output is correct
10 Correct 396 ms 55548 KB Output is correct
11 Correct 186 ms 41880 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14348 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 8 ms 14292 KB Output is correct
7 Correct 12 ms 14552 KB Output is correct
8 Correct 8 ms 14476 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct
10 Correct 13 ms 15060 KB Output is correct
11 Correct 9 ms 14932 KB Output is correct
12 Incorrect 10 ms 14804 KB Output isn't correct
13 Halted 0 ms 0 KB -