oj.uz

Submission #869674

# Submission time Handle Problem Language Result Execution time Memory
869674 2023-11-05T09:24:51 Z sleepntsheep Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 346 ms 29780 KB 
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")



using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005

int n, m, s, t, cs, ct, head[N], e, se, shead[N];
struct edge
{
    int w, v, next;
} g[N<<1], sg[N<<1];

ll dp_s[N], dp_t[N], dp_cs[N], dp_ct[N], ans = 1e18;

void add_edge(int u, int v, int w, struct edge *g, int *e, int *h)
{
    int p = (*e)++;
    g[p] = {w, v, h[u]}; h[u] = p;
}

void add_biedge(int u, int v, int w, struct edge *g, int *e, int *h)
{
    add_edge(u, v, w, g, e, h), add_edge(v, u, w, g, e, h);
}

void dijkstra(ll *d, int s)
{
    set<pair<ll, int>> h;
    for (h.emplace(d[s] = 0, s); h.size(); )
    {
        auto [c, u] = *h.begin(); h.erase(h.begin());
        for (auto i = head[u]; i != -1; i = g[i].next)
        {
            auto [w, v, _] = g[i];
            if (c + w < d[v]) h.erase({d[v], v}), h.emplace(d[v] = c + w, v);
        }
    }
}

void init()
{
    memset(dp_s, 63, sizeof dp_s);
    memset(dp_t, 63, sizeof dp_t);
    memset(dp_cs, 63, sizeof dp_cs);
    memset(dp_ct, 63, sizeof dp_ct);
    memset(head, -1, sizeof head);
    memset(shead, -1, sizeof shead);
    ShinLena;
    cin >> n >> m >> s >> t >> cs >> ct;
    for (int u, v, w, i = 0; i < m; ++i) cin >> u >> v >> w, add_biedge(u, v, w, g, &e, head);
}

void build_shortest_path_graph()
{
    dijkstra(dp_s, s);
    dijkstra(dp_t, t);
    for (int u = 1; u <= n; ++u)
    {
        for (int j = head[u]; j != -1; j = g[j].next)
        {
            auto [w, v, _] = g[j];
            if (dp_s[u] + dp_t[v] + w == dp_s[t] || w + dp_s[v] + dp_t[u] == dp_s[t])
                add_biedge(u, v, w, sg, &se, shead);
        }
    }
}

int low[N], tin[N], timer = 1, bridge[N<<1][2], bs;

void dfs(int u, int p)
{
    low[u] = tin[u] = timer++;
    for (auto j = shead[u]; j != -1; j = sg[j].next)
    {
        auto [w, v, _] = sg[j];
        if (v == p) continue;
        if (tin[v])
        {
            low[u] = min(low[u], tin[v]);
        }
        else
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u])
                bridge[bs][0] = u, bridge[bs][1] = v, ++bs;
        }
    }
}

void find_path()
{
    dijkstra(dp_cs, cs);
    dijkstra(dp_ct, ct);
    ll d1 = 1e18, d2 = 1e18;
    for (int i = 0; i < bs; ++i)
    {
        auto u = bridge[i][0], v = bridge[i][1];
        d1 = min({d1, dp_cs[u], dp_cs[v]});
        d2 = min({d2, dp_ct[u], dp_ct[v]});
    }
    ans = min(dp_cs[ct], d1 + d2);
}

int main()
{
    init();
    build_shortest_path_graph();
    dfs(s, s);
    find_path();
    cout << ans;

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 21588 KB Output is correct
2 Correct 229 ms 23636 KB Output is correct
3 Correct 219 ms 29524 KB Output is correct
4 Incorrect 247 ms 21400 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 25200 KB Output is correct
2 Correct 270 ms 24916 KB Output is correct
3 Correct 257 ms 24420 KB Output is correct
4 Correct 253 ms 24536 KB Output is correct
5 Correct 269 ms 27352 KB Output is correct
6 Correct 219 ms 29116 KB Output is correct
7 Correct 264 ms 29780 KB Output is correct
8 Correct 260 ms 24660 KB Output is correct
9 Correct 256 ms 27220 KB Output is correct
10 Correct 268 ms 24724 KB Output is correct
11 Correct 60 ms 27220 KB Output is correct
12 Correct 219 ms 29524 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 21588 KB Output is correct
2 Correct 229 ms 23636 KB Output is correct
3 Correct 219 ms 29524 KB Output is correct
4 Incorrect 247 ms 21400 KB Output isn't correct
5 Halted 0 ms 0 KB -