oj.uz

Submission #724821

# Submission time Handle Problem Language Result Execution time Memory
724821 2023-04-16T03:43:19 Z Cookie Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 27 ms 4652 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll 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[mxn + 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[s] = make_pair(-1, -1);
    }
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1; ll mn = 1e18;
        for(int j = 1; j <= n; j++){
            if(d[j] < mn && !vis[j]){
                u = j;
            }
        }
        vis[u] = true;
        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);
            }
        }
        if(u == U){
            if(d[V] > d[u] + W){
                d[V] = d[u] + W;
            }
        }
    }
    
}
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;
    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 != 1){
            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, d2[1][1] + 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 + edge[i].e; 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(int)':
ho_t4.cpp:54:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp: In function 'void D2(int)':
ho_t4.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         auto [u, type, dd] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |             for(auto [v, c, e, id]: rev[u]){
      |                      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 27 ms 472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 460 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 20 ms 3476 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 18 ms 4652 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 27 ms 472 KB Output isn't correct
4 Halted 0 ms 0 KB -