oj.uz

Submission #366802

# Submission time Handle Problem Language Result Execution time Memory
366802 2021-02-15T10:04:11 Z balbit Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 94 ms 9212 KB 
#include <bits/stdc++.h>
//#undef BALBIT
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 200+5;

struct edge{
    int v, u, w, d, i;
};

vector<edge> g[maxn], gt[maxn];
bool done[maxn], ban[50005];
int par[maxn];
ll d[maxn], rd[maxn];
int n,m;

ll dij(int S, int T, vector<edge> gee[], ll D[]){
//    return 3;
    assert(D[17] == 0x3f3f3f3f3f3f3f3f);
    memset (done, 0, sizeof done);
    D[S] = 0;
    while (1){
        ll w = inf; int v = -1;
        REP(i,n) {
            if (!done[i]) {
                if (D[i] < w) {
                    w = D[i]; v = i;
                }
            }
        }
        if (v == -1) break;
        done[v] = 1;
        for (edge & e : gee[v]) {
            if (e.i!=-1 && ban[e.i]) continue;
            if (D[e.u] > D[v] + e.w) {
                D[e.u] = D[v] + e.w;
                par[e.u] = e.i;
            }
        }
    }
    return D[T];
}

vector<edge> E;

ll go(int S = 0, int T = n-1) {
//    return -1;
    memset(ban, 0, sizeof ban);
    memset(par, -1, sizeof par);
    memset (d, 0x3f, sizeof d);
    ll re = dij(T, S, g, d);
    memset (d, 0x3f, sizeof d);
    ll straight = dij(S,T, g, d);
    re += straight; MN(re, inf);
    vector<int> pth;
    if (straight < inf){
        for (int at = T; par[at] !=-1 && at != S; ) {
            bug(par[at]);
            pth.pb(par[at]);
//            ban[par[at]] = 1;
            at = E[par[at]].v;
        }
    }
//    return -1;
    bug(straight);
    vector<int> tmp(m);
    {
        memset (d, 0x3f, sizeof d);
        memset (rd, 0x3f, sizeof rd);
        dij(T, S, gt, rd);
        dij(S, T, g,   d);
        REP(i, m) {
            edge &e = E[i];
            tmp[i] = e.w + rd[e.u] + d[e.v];
        }
    }
    memset (d, 0x3f, sizeof d);
    memset (rd, 0x3f, sizeof rd);
    dij(T, S, g, d);
    dij(S, T, gt,rd);
    for (int x : pth) ban[x] = 1;
    int nw = 0;
    for (edge &e : E) {
        if (!ban[e.i]) {
            MN(re, min(inf, min(straight,tmp[nw]) + min(inf, rd[e.v] + d[e.u])) + e.d + e.w);
//            if (e.i == 1) {
//                bug(e.v, e.u, rd[e.v]+ d[e.u]+ e.d+ e.w + straight);
//            }
        }
        ++nw;
//        bug(re);
    }
    memset(ban, 0, sizeof ban);
    for (int i : pth) {
//    REP(i,m){
        edge & e = E[i];
        ban[e.i] = 1; g[e.u].pb({e.u, e.v, e.w, e.d, -1});
        memset (d, 0x3f, sizeof d);
        ll t1 = dij(S,T,g,d);
        memset (d, 0x3f, sizeof d);
        ll t2 = dij(T,S,g,d);
        MN(re, t1+t2+e.d);
        g[e.u].pop_back();
        ban[e.i] = 0;
    }
    return re;
}

signed main(){
    IOS();
    cin>>n>>m;
    REP(i,m) {
        int a,b,w,p; cin>>a>>b>>w>>p; --a; --b;
        E.pb({a,b,w,p,i});
        g[a] .pb({a,b,w,p,i});
        gt[b].pb({b,a,w,p,i});
    }
    ll ans = go();
    bug(ans);
//    swap(g, gt);
//    for (edge & e : E) swap(e.v, e.u);
    ans = min(ans, go(n-1, 0));
    bug(ans);
    if (ans > inf/2) ans = -1;
    cout<<ans<<endl;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 7 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 94 ms 672 KB Output is correct
11 Correct 91 ms 620 KB Output is correct
12 Correct 89 ms 620 KB Output is correct
13 Incorrect 2 ms 640 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8956 KB Output is correct
2 Correct 35 ms 9212 KB Output is correct
3 Correct 35 ms 9212 KB Output is correct
4 Correct 5 ms 748 KB Output is correct
5 Correct 6 ms 620 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 30 ms 8828 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 25 ms 7552 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 30 ms 8828 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 35 ms 8828 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 7 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 94 ms 672 KB Output is correct
11 Correct 91 ms 620 KB Output is correct
12 Correct 89 ms 620 KB Output is correct
13 Incorrect 2 ms 640 KB Output isn't correct
14 Halted 0 ms 0 KB -