oj.uz

Submission #826022

# Submission time Handle Problem Language Result Execution time Memory
826022 2023-08-15T09:56:34 Z AmirElarbi Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 18 ms 3916 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e15
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace __gnu_pbds;
using namespace std;
const int nax = 1e4+5;
const int kax = 1e5+5;
const int MOD = 1e9+7;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int x[kax], y[kax];
ll c[kax], d[kax]; 
int n,m;
vi adj[2][nax];
ve<ll> dijkstra(int st, bool type){
    priority_queue<pair<ll,int>, ve<pair<ll,int>>, greater<pair<ll,int>>> pq;
    ve<ll> dist(n+1, INF);
    dist[st] = 0;
    pq.push({0ll, st});
    while(!pq.empty()){
        ll cst = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(dist[u] != cst) continue;
        for(auto j : adj[type][u]){
            int to = y[j];
            if(type) to = x[j];
            if(dist[to] > (c[j] + dist[u])){
                dist[to] = c[j] + dist[u];
                pq.push({dist[to], to});
            }
        }
    }
    return dist;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> x[i] >> y[i] >> c[i] >> d[i];
        adj[0][x[i]].pb(i);
        adj[1][y[i]].pb(i);
    }
    ve<ll>  dist1 = dijkstra(1, 0);
    ve<ll>  distn = dijkstra(n, 0);
    ve<ll>  distrev1 = dijkstra(1, 1);
    ve<ll>  distrevn = dijkstra(n, 1);
    ll aff = min(dist1[n] + distn[1], (ll)INF);
    for (int i = 0; i < m; ++i)
    {
        aff = min(aff, dist1[y[i]] + distrevn[x[i]] + distn[1] + c[i] + d[i]);
        aff = min(aff, dist1[n] + distn[y[i]] + distrev1[x[i]] + c[i] + d[i]);
        aff = min(aff, dist1[y[i]] + distrevn[x[i]] + distn[y[i]] + distrev1[x[i]] + 2*c[i] + d[i]);
    }
    if(aff == INF) cout << -1 << endl;
    else cout << aff << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3628 KB Output is correct
2 Correct 14 ms 3672 KB Output is correct
3 Correct 15 ms 3868 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 800 KB Output is correct
9 Correct 15 ms 3824 KB Output is correct
10 Correct 14 ms 3764 KB Output is correct
11 Correct 14 ms 3720 KB Output is correct
12 Correct 18 ms 3828 KB Output is correct
13 Correct 15 ms 3856 KB Output is correct
14 Correct 16 ms 3916 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 11 ms 2816 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 14 ms 3484 KB Output is correct
6 Incorrect 1 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Halted 0 ms 0 KB -