oj.uz

Submission #826116

# Submission time Handle Problem Language Result Execution time Memory
826116 2023-08-15T10:30:53 Z AmirElarbi Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 20 ms 3924 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];
set<int> way1, way2;
ve<ll> dijkstra(int st, bool type, int del){
    priority_queue<pair<ll,int>, ve<pair<ll,int>>, greater<pair<ll,int>>> pq;
    ve<ll> dist(n+1, INF);
    dist[st] = 0;
    vi par(n+1,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]){
            if(j == del) continue;
            int to = y[j];
            if(type) to = x[j];
            if(dist[to] > (c[j] + dist[u])){
                dist[to] = c[j] + dist[u];
                par[to] = j;
                pq.push({dist[to], to});
            }
        }
        if(del != -1 && u == y[del] && dist[x[del]] > (c[del] + dist[u])){
            dist[x[del]] = c[del] + dist[u];
            pq.push({dist[x[del]], x[del]});
        }
    }
    if(way1.size() == 0){
        if(dist[n] == INF) way1.insert(-1);
        int u = n;
        while(par[u]){
            way1.insert(par[u]);
            u = x[par[u]];
        }
    } else if(way2.size() == 0){
        if(dist[1] == INF) way2.insert(-1);
        int u = 1;
        while(par[u]){
            way2.insert(par[u]);
            u = x[par[u]];
        }
    }
    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, -1), distn = dijkstra(n, 0, -1), distrev1 = dijkstra(1, 1, -1) , distrevn = dijkstra(n, 1, -1);
    ll aff = min(dist1[n] + distn[1], (ll)INF);
    for (int i = 0; i < m; ++i)
    {
        if(!way1.count(i) && !way2.count(i)){
            aff = min(aff, dist1[y[i]] + distrevn[x[i]] + distn[y[i]] + distrev1[x[i]] + 2*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[1] + c[i] + d[i]);
        } else {
            ve<ll>  cur1 = dijkstra(1, 0, i), curn = dijkstra(n, 0, i);
            aff = min(aff, cur1[n] + curn[1] + 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 2 ms 852 KB Output is correct
2 Correct 1 ms 800 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Correct 2 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 20 ms 3656 KB Output is correct
2 Correct 18 ms 3596 KB Output is correct
3 Correct 19 ms 3844 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 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 724 KB Output is correct
9 Correct 19 ms 3704 KB Output is correct
10 Correct 15 ms 3768 KB Output is correct
11 Correct 18 ms 3748 KB Output is correct
12 Correct 17 ms 3800 KB Output is correct
13 Correct 18 ms 3768 KB Output is correct
14 Correct 17 ms 3924 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 812 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 12 ms 2944 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 14 ms 3540 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 2 ms 852 KB Output is correct
2 Correct 1 ms 800 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Correct 2 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 -