oj.uz

Submission #363922

# Submission time Handle Problem Language Result Execution time Memory
363922 2021-02-07T14:16:31 Z Lam_lai_cuoc_doi Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 383 ms 2352 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 2e2 + 5;
const int M = 5e4 + 5;
const ll Inf = 1e17;
struct Edge
{
    int u, v, c;
    ll d;
    bool operator<(const Edge &a) const
    {
        return v < a.v || (v == a.v && c < a.c) || (v == a.v && c == a.c && d < a.d);
    }
} e[M];
vector<int> adj[N], nadj[N];
int n, m;
ll d[7][N];
bitset<M> ck[7], chosen;
ll ans(Inf);

void Read()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d;
        adj[e[i].u].push_back(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        sort(adj[i].begin(), adj[i].end(), [&](const int &x, const int &y) {
            return e[x] < e[y];
        });
        int p(0);
        for (int j = 0; j < (int)adj[i].size(); ++j)
        {
            int t = j;
            while (t < (int)adj[i].size() && e[adj[i][t]].v == e[adj[i][j]].v)
                ++t;
            if (t - j > 2)
            {
                adj[i][p++] = adj[i][j];
                adj[i][p++] = adj[i][j + 1];
                j = t - 1;
            }
            else
            {
                while (j < t)
                    adj[i][p++] = adj[i][j++];
                --j;
            }
        }
        adj[i].resize(p);
        for (auto j : adj[i])
        {
            chosen[j] = 1;
            nadj[e[j].v].push_back(j);
        }
    }
}

void Dijkstra(int x, vector<int> adj[N], ll d[N], bitset<M> &ck, int except)
{
    fill_n(&d[0], N, Inf);
    vector<bool> ok(n + 1, 0);
    vector<int> par(n + 1);
    d[x] = 0;
    while (1)
    {
        int v(0);
        for (int i = 1; i <= n; ++i)
            if (!ok[i] && d[v] > d[i])
                v = i;
        if (v == 0)
            break;
        ok[v] = 1;
        for (auto i : adj[v])
            if (i != except && d[e[i].v ^ e[i].u ^ v] > d[v] + e[i].c)
            {
                d[e[i].v ^ e[i].u ^ v] = d[v] + e[i].c;
                par[e[i].v ^ e[i].u ^ v] = i;
            }
    }
    if (except == 0)
    {
        for (int i = 1; i <= n; ++i)
            if (i != x && d[i] != Inf)
            {
                ck[par[i]] = 1;
            }
    }
}

ll Proc(int i, int x, int y, const vector<int> &s)
{
    ll res(0);
    int tmp1(s[0]), tmp2(s[3]);
    if (ck[s[0]][i])
    {
        Dijkstra(x, adj, d[5], ck[5], i);
        tmp1 = 5;
    }
    if (ck[s[3]][i])
    {
        Dijkstra(y, nadj, d[6], ck[6], i);
        tmp2 = 6;
    }
    if (d[tmp1][e[i].v] == Inf || d[tmp2][e[i].u] == Inf)
        return Inf;
    res = d[tmp1][e[i].v] + e[i].c + e[i].d + d[tmp2][e[i].u];
    tmp1 = s[2];
    if (ck[s[2]][i])
    {
        Dijkstra(y, adj, d[5], ck[5], i);
        tmp1 = 5;
    }
    if (d[tmp1][x] == Inf)
        return Inf;
    res += d[tmp1][x];
    return res;
}

void Solve()
{
    Dijkstra(1, adj, d[1], ck[1], 0);
    Dijkstra(1, nadj, d[2], ck[2], 0);
    Dijkstra(n, adj, d[3], ck[3], 0);
    Dijkstra(n, nadj, d[4], ck[4], 0);
    if (d[1][n] != Inf && d[3][1] != Inf)
        ans = d[1][n] + d[3][1];
    for (int i = 1; i <= m; ++i)
        if (chosen[i])
        {
            ans = min(ans, Proc(i, 1, n, {1, 2, 3, 4}));
            ans = min(ans, Proc(i, n, 1, {3, 4, 1, 2}));
        }
    cout << (ans == Inf ? -1 : ans);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 488 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 148 ms 364 KB Output is correct
4 Correct 150 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 9 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 2224 KB Output is correct
2 Correct 370 ms 2284 KB Output is correct
3 Correct 367 ms 2156 KB Output is correct
4 Correct 156 ms 492 KB Output is correct
5 Correct 128 ms 512 KB Output is correct
6 Correct 22 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 73 ms 2108 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 364 KB Output is correct
2 Correct 18 ms 364 KB Output is correct
3 Correct 325 ms 1772 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 383 ms 2228 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 92 ms 2352 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 488 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 148 ms 364 KB Output is correct
4 Correct 150 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 9 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -