oj.uz

Submission #751762

# Submission time Handle Problem Language Result Execution time Memory
751762 2023-06-01T11:47:36 Z Kihihihi Robot (JOI21_ho_t4) C++17
34 / 100
 3000 ms 124044 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.99)
        {
            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 6 ms 11988 KB Output is correct
7 Correct 9 ms 12500 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 184 ms 13268 KB Output is correct
10 Correct 119 ms 13188 KB Output is correct
11 Correct 49 ms 13152 KB Output is correct
12 Correct 39 ms 12868 KB Output is correct
13 Correct 115 ms 13148 KB Output is correct
14 Correct 151 ms 13144 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 15 ms 12832 KB Output is correct
17 Correct 13 ms 13016 KB Output is correct
18 Correct 7 ms 12444 KB Output is correct
19 Correct 13 ms 12860 KB Output is correct
20 Correct 11 ms 12628 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 59032 KB Output is correct
2 Correct 228 ms 32340 KB Output is correct
3 Correct 147 ms 49916 KB Output is correct
4 Correct 141 ms 37396 KB Output is correct
5 Execution timed out 3080 ms 124044 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 6 ms 11988 KB Output is correct
7 Correct 9 ms 12500 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 184 ms 13268 KB Output is correct
10 Correct 119 ms 13188 KB Output is correct
11 Correct 49 ms 13152 KB Output is correct
12 Correct 39 ms 12868 KB Output is correct
13 Correct 115 ms 13148 KB Output is correct
14 Correct 151 ms 13144 KB Output is correct
15 Correct 9 ms 12500 KB Output is correct
16 Correct 15 ms 12832 KB Output is correct
17 Correct 13 ms 13016 KB Output is correct
18 Correct 7 ms 12444 KB Output is correct
19 Correct 13 ms 12860 KB Output is correct
20 Correct 11 ms 12628 KB Output is correct
21 Correct 526 ms 59032 KB Output is correct
22 Correct 228 ms 32340 KB Output is correct
23 Correct 147 ms 49916 KB Output is correct
24 Correct 141 ms 37396 KB Output is correct
25 Execution timed out 3080 ms 124044 KB Time limit exceeded
26 Halted 0 ms 0 KB -