oj.uz

Submission #751763

# Submission time Handle Problem Language Result Execution time Memory
751763 2023-06-01T11:48:03 Z Kihihihi Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 124144 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, c, p;
};

long long n;
vector<edge> g[100000];
map<long long, long long> emp[100000], cnte[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].push_back({ b, c, p });
        g[b].push_back({ a, c, p });
    }
    for (long long i = 0; i < n; i++)
    {
        for (auto& j : g[i])
        {
            emp[i][j.c] += j.p;
            cnte[i][j.c]++;
        }
        shuffle(g[i].begin(), g[i].end(), rnd);
    }

    vector<vector<unordered_map<long long, long long>>> dist(n, vector<unordered_map<long long, long long>>(2));
    dist[0][0][0] = 0;
    for (long long i = 1; i < n; i++)
    {
        for (long long _ = 0; _ < 2; _++)
        {
            dist[i][_].reserve(g[i].size());
            for (auto& j : g[i])
            {
                dist[i][_][j.to] = INF;
            }
        }
    }

    long long ans = INF;
    set<tuple<long long, long long, long long, bool>> q = { { 0, 0, 0, 0 } };
    while (q.size())
    {
        if (clock() / (double)CLOCKS_PER_SEC >= 2.95)
        {
            break;
        }
        auto [d, v, fr, ch] = *q.begin();
        q.erase(q.begin());
        if (d >= ans)
        {
            continue;
        }

        if (ch)
        {
            for (auto& i : g[v])
            {
                if (i.to == fr)
                {
                    emp[v][i.c] -= i.p;
                    cnte[v][i.c]--;
                    break;
                }
            }
        }
        for (auto& i : g[v])
        {
            if (i.to == fr || i.to == 0)
            {
                continue;
            }
            
            long long add[2] = { emp[v][i.c] - i.p, i.p };
            for (long long _ = 0; _ < 2; _++)
            {
                if (d + add[_] < dist[i.to][_][v])
                {
                    q.erase({ dist[i.to][_][v], i.to, v, _ });
                    dist[i.to][_][v] = d + add[_];
                    q.insert({ dist[i.to][_][v], i.to, v, _ });

                    if (i.to == n - 1)
                    {
                        ans = min(ans, d + add[_]);
                    }
                }
            }
        }
        if (ch)
        {
            for (auto& i : g[v])
            {
                if (i.to == fr)
                {
                    emp[v][i.c] += i.p;
                    cnte[v][i.c]++;
                    break;
                }
            }
        }
    }
    cout << (ans == INF ? -1 : ans) << "\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 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 9 ms 12508 KB Output is correct
8 Correct 7 ms 12240 KB Output is correct
9 Correct 190 ms 13268 KB Output is correct
10 Correct 112 ms 13140 KB Output is correct
11 Correct 50 ms 13140 KB Output is correct
12 Correct 40 ms 12896 KB Output is correct
13 Correct 100 ms 13132 KB Output is correct
14 Correct 150 ms 13140 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 15 ms 12844 KB Output is correct
17 Correct 13 ms 12884 KB Output is correct
18 Correct 7 ms 12372 KB Output is correct
19 Correct 12 ms 12884 KB Output is correct
20 Correct 11 ms 12580 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 59168 KB Output is correct
2 Correct 228 ms 32256 KB Output is correct
3 Correct 145 ms 49892 KB Output is correct
4 Correct 147 ms 37420 KB Output is correct
5 Execution timed out 3074 ms 124144 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 9 ms 12508 KB Output is correct
8 Correct 7 ms 12240 KB Output is correct
9 Correct 190 ms 13268 KB Output is correct
10 Correct 112 ms 13140 KB Output is correct
11 Correct 50 ms 13140 KB Output is correct
12 Correct 40 ms 12896 KB Output is correct
13 Correct 100 ms 13132 KB Output is correct
14 Correct 150 ms 13140 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 15 ms 12844 KB Output is correct
17 Correct 13 ms 12884 KB Output is correct
18 Correct 7 ms 12372 KB Output is correct
19 Correct 12 ms 12884 KB Output is correct
20 Correct 11 ms 12580 KB Output is correct
21 Correct 512 ms 59168 KB Output is correct
22 Correct 228 ms 32256 KB Output is correct
23 Correct 145 ms 49892 KB Output is correct
24 Correct 147 ms 37420 KB Output is correct
25 Execution timed out 3074 ms 124144 KB Time limit exceeded
26 Halted 0 ms 0 KB -