oj.uz

Submission #779551

# Submission time Handle Problem Language Result Execution time Memory
779551 2023-07-11T14:14:37 Z 1bin Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 33 ms 5672 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const ll inf = 1e18;
const int MX = 5e4 + 5;
ll n, m, a[MX], b[MX], c[MX], d[MX], ans, chk[2][MX], mnd[2], d1, d2, D[4][205];
vector<pair<ll, ll>> adj[205], rev[205];

ll dijk(int s, int e, int f){
    int t = n + 1 - s;
    vector<ll> dist(n + 1, inf);
    vector<int> E(n + 1, 0), vis(n + 1, 0);
    dist[s] = 0;
    while(1){
        ll mn = inf, x;
        for(int i = 1; i <= n; i++)
            if(!vis[i] && dist[i] < mn) mn = dist[i], x = i;
        if(mn == inf) break;
        vis[x] = 1;
        if(f == 1 || f == 3){
            for(auto&[nx, ix] : rev[x])
                if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
        }
        else{
            for(auto&[nx, ix] : adj[x])
                if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
        }
    }
    if(f >= 4){
        f -= 4;
        if(dist[t] == inf) return inf;
        for(int x = t; x != s; x = a[E[x]]) chk[f][E[x]] = 1;
    }
    else if(f >= 0) {
        for(int i = 1; i <= n; i++) D[f][i] = dist[i];
    }
    return dist[t];
}


int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        adj[a[i]].emplace_back(b[i], i);
        rev[b[i]].emplace_back(a[i], i);
    }
    dijk(1, -1, 0);
    dijk(n, -1, 1);
    dijk(n, -1, 2);
    dijk(1, -1, 3);
    mnd[0] = dijk(1, -1, 4);
    mnd[1] = dijk(n, -1, 5);
    ans = mnd[0] + mnd[1];
    for(int i = 0; i < m; i++){
        adj[b[i]].emplace_back(a[i], m);
        c[m] = c[i] + d[i];
        if(!chk[0][i]) d1 = min(mnd[0], D[0][b[i]] + c[i] + d[i] + D[1][a[i]]);
        else d1 = dijk(1, i, -1);
        if(!chk[1][i]) d2 = min(mnd[1], D[2][b[i]] + c[i] + d[i] + D[3][a[i]]);
        else d2 = dijk(n, i, -1);
        //cout << d1 << ' ' << d2 << '\n';
        ans = min(ans, d1 + d2);
        adj[b[i]].pop_back();
    }
    cout << (ans >= inf ? -1 : ans);
    return 0;
}

Compilation message

ho_t4.cpp: In function 'll dijk(int, int, int)':
ho_t4.cpp:24:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |             for(auto&[nx, ix] : rev[x])
      |                      ^
ho_t4.cpp:28:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |             for(auto&[nx, ix] : adj[x])
      |                      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 472 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 33 ms 468 KB Output is correct
11 Correct 32 ms 468 KB Output is correct
12 Correct 32 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5632 KB Output is correct
2 Correct 17 ms 5588 KB Output is correct
3 Correct 18 ms 5672 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 16 ms 5520 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 12 ms 4156 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 20 ms 5380 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 14 ms 5340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 472 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 33 ms 468 KB Output is correct
11 Correct 32 ms 468 KB Output is correct
12 Correct 32 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -