oj.uz

Submission #1063107

# Submission time Handle Problem Language Result Execution time Memory
1063107 2024-08-17T14:17:10 Z _8_8_ Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 136 ms 6852 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;
    
const ll inf = 1e16;
int n,m;
int U[N],V[N],C[N],D[N];
void dijkstra(int ver,vector<ll> &d,vector<int> &pr) {
    d.resize(n);
    pr.resize(n);
    for(int i = 0;i < n;i++) {
        d[i] = inf;
    }
    d[ver] = 0;
    vector<int> vis(n,0);
    vector<vector<int>> g;g.resize(n);
    for(int i = 0;i < m;++i) {
        g[U[i]].push_back(i);
    }
    for(int i = 0;i < n;i++) {
        int v = -1;
        for(int j = 0;j < n;j++) {
            if(vis[j]) continue;
            if(v == -1 || d[j] < d[v]) {
                v = j;
            }
        }
        // cerr << v << '\n';
        vis[v] = 1;
        for(int t:g[v]) {
            int to = V[t],w = C[t];
            if(d[to] > d[v] + w) {
                d[to] = d[v] + w;
                pr[to] = t;
            }
        }
    }
}
vector<ll> d[N];
vector<int> p[N];
ll res = inf;
bool in[N];
void test() {
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        cin >> U[i] >> V[i] >> C[i] >> D[i];
        U[i]--;V[i]--;
    }
    for(int i = 0;i < n;++i) {
        dijkstra(i,d[i],p[i]);
    }
    res = d[0][n-1] + d[n - 1][0];
    vector<ll> bfd;
    vector<int> bfp;
    auto make = [&](int x,int y,vector<int> &pr){
        while(x != y) {
            int j = pr[x];
            in[j] = 1;
            swap(V[j],U[j]);
            ll nv = D[j];
            // cout << j << ' ';
            dijkstra(0,bfd,bfp);
            nv += bfd[n - 1];
            dijkstra(n - 1,bfd,bfp);
            nv += bfd[0];
            res = min(res,nv);
            swap(V[j],U[j]);
            x = U[j];
        }
    };
    if(d[0][n - 1] != inf) make(n - 1,0,p[0]);
    if(d[n - 1][0] != inf) make(0,n - 1,p[n - 1]);
    for(int i = 0;i < m;i++) {
        if(in[i]) continue;
        swap(U[i],V[i]);
        ll val = min(d[0][n - 1],d[0][U[i]] + d[V[i]][n - 1] + C[i] + D[i]);
        val += min(d[n - 1][0],d[n - 1][U[i]] + d[V[i]][0] + C[i] + D[i]);
        res = min(res,val);
    }
    if(res >= inf) res = -1;
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5464 KB Output is correct
2 Correct 19 ms 5464 KB Output is correct
3 Correct 30 ms 5484 KB Output is correct
4 Correct 24 ms 5656 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 23 ms 5552 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 90 ms 5588 KB Output is correct
11 Correct 95 ms 5464 KB Output is correct
12 Correct 95 ms 5668 KB Output is correct
13 Incorrect 20 ms 5468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 6844 KB Output is correct
2 Correct 112 ms 6852 KB Output is correct
3 Correct 111 ms 6848 KB Output is correct
4 Correct 25 ms 5468 KB Output is correct
5 Correct 30 ms 5604 KB Output is correct
6 Correct 18 ms 5468 KB Output is correct
7 Correct 17 ms 5468 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Incorrect 99 ms 6816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5464 KB Output is correct
2 Correct 22 ms 5468 KB Output is correct
3 Correct 104 ms 6364 KB Output is correct
4 Correct 16 ms 5468 KB Output is correct
5 Correct 108 ms 6824 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Incorrect 98 ms 6788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5464 KB Output is correct
2 Correct 19 ms 5464 KB Output is correct
3 Correct 30 ms 5484 KB Output is correct
4 Correct 24 ms 5656 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 23 ms 5552 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 90 ms 5588 KB Output is correct
11 Correct 95 ms 5464 KB Output is correct
12 Correct 95 ms 5668 KB Output is correct
13 Incorrect 20 ms 5468 KB Output isn't correct
14 Halted 0 ms 0 KB -