oj.uz

Submission #366797

# Submission time Handle Problem Language Result Execution time Memory
366797 2021-02-15T09:55:52 Z balbit Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 93 ms 9852 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);
    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;
    for (edge &e : E) {
        if (!ban[e.i]) {
            MN(re, min(inf, straight + 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);
//            }
        }
//        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 5 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 6 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 512 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 91 ms 620 KB Output is correct
11 Correct 93 ms 620 KB Output is correct
12 Correct 93 ms 620 KB Output is correct
13 Incorrect 2 ms 620 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8300 KB Output is correct
2 Correct 33 ms 9340 KB Output is correct
3 Correct 34 ms 9852 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 5 ms 620 KB Output is correct
6 Correct 1 ms 492 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 9340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 24 ms 7424 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 31 ms 8832 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 27 ms 8848 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 6 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 512 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 91 ms 620 KB Output is correct
11 Correct 93 ms 620 KB Output is correct
12 Correct 93 ms 620 KB Output is correct
13 Incorrect 2 ms 620 KB Output isn't correct
14 Halted 0 ms 0 KB -