oj.uz

Submission #751830

# Submission time Handle Problem Language Result Execution time Memory
751830 2023-06-01T14:50:55 Z Kihihihi Robot (JOI21_ho_t4) C++17
24 / 100
 1280 ms 92164 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;
                if (add < 0)
                {
                    continue;
                }
                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 14396 KB Output is correct
2 Correct 10 ms 14360 KB Output is correct
3 Correct 9 ms 14292 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 12 ms 15188 KB Output is correct
10 Correct 11 ms 15056 KB Output is correct
11 Correct 10 ms 14804 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 233 ms 36532 KB Output is correct
2 Correct 93 ms 25932 KB Output is correct
3 Correct 173 ms 31424 KB Output is correct
4 Correct 122 ms 29388 KB Output is correct
5 Correct 1280 ms 92164 KB Output is correct
6 Correct 955 ms 80196 KB Output is correct
7 Correct 381 ms 62936 KB Output is correct
8 Correct 442 ms 52248 KB Output is correct
9 Correct 447 ms 52164 KB Output is correct
10 Correct 407 ms 53160 KB Output is correct
11 Correct 175 ms 40092 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14396 KB Output is correct
2 Correct 10 ms 14360 KB Output is correct
3 Correct 9 ms 14292 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 12 ms 15188 KB Output is correct
10 Correct 11 ms 15056 KB Output is correct
11 Correct 10 ms 14804 KB Output is correct
12 Incorrect 10 ms 14804 KB Output isn't correct
13 Halted 0 ms 0 KB -