oj.uz

Submission #752983

# Submission time Handle Problem Language Result Execution time Memory
752983 2023-06-04T11:43:48 Z Kihihihi Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 5176 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 = 1e17, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

struct edge
{
    long long to, w, idx;
};

long long n;
vector<edge> g[200];

void spfa(long long s, long long rv, vector<long long>& dist)
{
    dist[s] = 0;
    deque<long long> q = { s };
    vector<bool> in_q(n);
    in_q[s] = true;
    while (q.size())
    {
        long long v = q.front();
        q.pop_front();
        in_q[v] = false;
        for (auto& i : g[v])
        {
            if (i.idx == rv)
            {
                continue;
            }
            if (i.idx < 0 && i.idx != -rv)
            {
                continue;
            }

            if (dist[i.to] > dist[v] + i.w)
            {
                dist[i.to] = dist[v] + i.w;
                if (!in_q[i.to])
                {
                    q.push_back(i.to);
                    in_q[i.to] = true;
                }
            }
        }
    }
}

void solve()
{
    long long m;
    cin >> n >> m;
    vector<long long> rv(m);
    for (long long i = 0; i < m; i++)
    {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--;
        g[a].push_back({ b, c, i + 1 });
        g[b].push_back({ a, c, -(i + 1) });
        rv[i] = d;
    }
    for (long long i = 0; i < n; i++)
    {
        shuffle(g[i].begin(), g[i].end(), rnd);
    }

    long long ans = INF;
    vector<long long> dist(n, INF);
    for (long long i = 0; i < m + 1; i++)
    {
        long long cur = 0;
        if (i >= 1)
        {
            cur = rv[i - 1];
        }
        if (cur >= ans)
        {
            continue;
        }

        dist.assign(n, INF);
        spfa(0, i, dist);
        cur += dist[n - 1];
        if (cur >= ans)
        {
            continue;
        }

        dist.assign(n, INF);
        spfa(n - 1, i, dist);
        cur += dist[0];
        ans = min(ans, cur);
    }
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 181 ms 424 KB Output is correct
11 Correct 194 ms 428 KB Output is correct
12 Correct 203 ms 424 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 39 ms 428 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 22 ms 344 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 5176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 23 ms 4004 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 24 ms 5024 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 34 ms 5008 KB Output is correct
9 Correct 47 ms 5012 KB Output is correct
10 Execution timed out 1071 ms 4984 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 181 ms 424 KB Output is correct
11 Correct 194 ms 428 KB Output is correct
12 Correct 203 ms 424 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 39 ms 428 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 22 ms 344 KB Output is correct
17 Execution timed out 1070 ms 5176 KB Time limit exceeded
18 Halted 0 ms 0 KB -