oj.uz

Submission #724841

# Submission time Handle Problem Language Result Execution time Memory
724841 2023-04-16T04:40:59 Z Cookie Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 28 ms 8012 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define int long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 205, mxm = 50005;

struct ch{
    int u, type; ll dd;
};
struct E{
    int u, v, c, e;
};
int n, m;
vt<E>adj[mxn + 1], rev[mxn + 1];
E edge[mxm + 1];
bool used1[mxm + 1], vis[mxn + 1], usedn[mxm + 1];
pii trace[mxn + 1];
ll d[mxn + 1], d2[mxn + 1][2];
ll U = -1, V, W, ID = -1;
struct cmp{
    bool operator()(const ch &a, const ch &b){
        return(a.dd > b.dd);
    }
};
void D(int s){
    
    forr(i, 1, n + 1){
        d[i] = 1e18; vis[i] = false;
        trace[i] = make_pair(-1, -1);
    }
    d[s] = 0; 
    priority_queue<pll, vt<pll>, greater<pll>>pq; pq.push({d[s], s});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        if(d[u] != dd)continue;
        for(auto [v, c, e, id]: adj[u]){
            if(id == ID)continue;
            if(d[v] > d[u] + c){
                d[v] = d[u] + c; trace[v] = make_pair(id, u);
                pq.push({d[v], v});
            }
        }
        if(u == U){
            if(d[V] > d[U] + W){
                d[V] = d[U] + W;
                pq.push({d[V], V});
            }
        }
    }
}
void D2(int s){
    forr(i, 1, n + 1){
        d2[i][0] = d2[i][1] = 1e18; vis[i] = false;
        
    }
    priority_queue<ch, vt<ch>, cmp>pq; d2[s][0] = 0; pq.push({s, 0, d2[s][0]});
    while(!pq.empty()){
        auto [u, type, dd] = pq.top(); pq.pop();
        if(d2[u][type] != dd)continue;
        for(auto [v, c, e, id]: adj[u]){
            
            if(d2[v][type] > d2[u][type] + c){
                d2[v][type] = d2[u][type] + c;
                pq.push({v, type, d2[v][type]});
            }
        }
        if(type == 0){
            for(auto [v, c, e, id]: rev[u]){
                if((s == 1 && usedn[id]) || (s == n && used1[id]))continue;
                if(d2[v][1] > d2[u][0] + c + e){
                    d2[v][1] = d2[u][0] + c + e;
                    pq.push({v, 1, d2[v][1]});
                }
            }
        }
    }
}
signed main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ID = -1;
    forr(i, 0, m){
        int u, v, c, e; cin >> u >> v >> c >> e;
        adj[u].pb({v, c, e, i}); rev[v].pb({u, c, e, i});
        edge[i] = {u, v, c, e};
    }
    bool ok1 = true, ok2 = true;
    
    D(1);
    
    ll dn = 1e18, d1 = 1e18;
    if(d[n]  < 1e18){
        ok1 = false;
        dn = d[n];
        int v = n;
        while(v != 1){
            used1[trace[v].fi] = 1;
            v = trace[v].se;
        }
    }
    D(n);
    if(d[1] < 1e18){
        d1 = d[1];
        ok2 = false;
        int v = 1;
        while(v != n){
            usedn[trace[v].fi] = 1;
            v = trace[v].se;
        }
    }
  
    //all edge from dijkstra Path -> o(n) Path
    ll ans = d1 + dn;
    
    if(ok1 && ok2){
        cout << -1; return(0);
    }
    if(!ok1){
        D2(n);
        
        ans = min(ans, min(d2[1][1], d2[1][0]) + dn);
    }if(!ok2){
        D2(1);
        ans = min(ans, d2[n][1] + d1);
    }
    forr(i, 0, m){
        if(used1[i] || usedn[i]){
            
            ll curr = 0;
            U = edge[i].v; V = edge[i].u; W = edge[i].c; ID = i;
            D(1); curr += d[n];
            D(n); curr += d[1];
            ans = min(ans, curr + edge[i].e);
        }
    }
    
    if(ans >= 1e18){
        cout << -1;
    }else{
        cout << ans;
    }
    
    return(0);
}

Compilation message

ho_t4.cpp: In function 'void D(long long int)':
ho_t4.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp: In function 'void D2(long long int)':
ho_t4.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto [u, type, dd] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp:83:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |             for(auto [v, c, e, id]: rev[u]){
      |                      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 15 ms 468 KB Output is correct
11 Correct 20 ms 468 KB Output is correct
12 Correct 20 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 26 ms 6988 KB Output is correct
2 Correct 24 ms 7796 KB Output is correct
3 Correct 25 ms 8012 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 21 ms 7652 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 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 15 ms 5216 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 28 ms 6728 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 18 ms 6872 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 484 KB Output is correct
10 Correct 15 ms 468 KB Output is correct
11 Correct 20 ms 468 KB Output is correct
12 Correct 20 ms 468 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -