oj.uz

Submission #363967

# Submission time Handle Problem Language Result Execution time Memory
363967 2021-02-07T17:33:09 Z Lam_lai_cuoc_doi Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 382 ms 3436 KB 
/// --- First time do a problem myself --- ///
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#define task "busline"
using namespace std;
using ll = long long;
using ld = long double;

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];
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);
        nadj[i].reserve(p);
        for (auto j : adj[i])
            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)
    {
        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_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}

Compilation message

ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  153 |         freopen(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  154 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 492 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 136 ms 492 KB Output is correct
4 Correct 141 ms 512 KB Output is correct
5 Correct 2 ms 492 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 Correct 1 ms 364 KB Output is correct
10 Correct 152 ms 508 KB Output is correct
11 Correct 141 ms 620 KB Output is correct
12 Correct 137 ms 492 KB Output is correct
13 Incorrect 24 ms 492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 3224 KB Output is correct
2 Correct 382 ms 3052 KB Output is correct
3 Correct 355 ms 3436 KB Output is correct
4 Correct 142 ms 492 KB Output is correct
5 Correct 115 ms 768 KB Output is correct
6 Correct 21 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 74 ms 3308 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 492 KB Output is correct
2 Correct 19 ms 492 KB Output is correct
3 Correct 318 ms 2540 KB Output is correct
4 Correct 10 ms 364 KB Output is correct
5 Correct 369 ms 3052 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 3180 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 492 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 136 ms 492 KB Output is correct
4 Correct 141 ms 512 KB Output is correct
5 Correct 2 ms 492 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 Correct 1 ms 364 KB Output is correct
10 Correct 152 ms 508 KB Output is correct
11 Correct 141 ms 620 KB Output is correct
12 Correct 137 ms 492 KB Output is correct
13 Incorrect 24 ms 492 KB Output isn't correct
14 Halted 0 ms 0 KB -