oj.uz

Submission #570886

# Submission time Handle Problem Language Result Execution time Memory
570886 2022-05-31T13:41:18 Z balbit Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 217232 KB 
#include "escape_route.h"

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#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);}

//const int maxn = 1e5+5;
namespace {
    const int N = 91;
    bool E[N][N]; // can a reach b, given a full day?
    ll L[N][N], C[N][N];
    int S;
    vector<ll> stime[N]; // stime i means the following distance info is for times [i, next)
    vector<vector<ll> > dst[N];

    int n;
    int from[N];
    bool done[N];

    int daydst[N][N];
    ll totdst[N][N];
}

ll dij(int v, ll T) {
    // returns the next closest edge to being unpassable

    bug(v, T);

    memset(from, -1, sizeof from);
    memset(done, 0, sizeof done);
    vector<ll> D(n,inf);
    D[v] = 0;
    ll re = inf;
    REP(round, n) {
        int at = -1, w = inf;
        REP(i,n) {
            if (!done[i] && D[i] < w) {
                at = i; w = D[i];
            }
        }
        if (at == -1) break;
        done[at] = 1;
        if (from[at] != -1) MN(re, C[at][from[at]] - D[at]);
        REP(j,n) {
            if (L[at][j] && !done[j] && C[at][j] - D[at] - L[at][j] >= T && D[j] > D[at] + L[at][j]) {
//                bug(at, j);
                if (v == 0) {
                    bug(j,at,L[at][j], D[at]);
                }
                D[j] = D[at] + L[at][j];
                from[j] = at;
            }
        }
    }
    assert(re >= 0);
    stime[v].pb(T);
    dst[v].pb(D);

    if (T == 0) {
        REP(j,n) {
            E[v][j] = D[j] < inf;
            bug(v,j,E[v][j]);
        }
    }

    return re;
}

void bfs(int st) {
    int *D = daydst[st];
    memset(daydst[st], 0x3f, sizeof daydst[st]);
    D[st] = 0;
    queue<int> q; q.push(st);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        REP(j,n) {
            if (E[v][j] && D[j] > D[v] + 1) {
                D[j] = D[v] + 1;
                q.push(j);
            }
        }
    }
}

std::vector<long long> calculate_necessary_time(
    signed en, signed M, long long eS, signed Q, std::vector<signed> eA, std::vector<signed> eB,
    std::vector<long long> eL, std::vector<long long> eC, std::vector<signed> U,
    std::vector<signed> V, std::vector<long long> eT) {

    S = eS;
    n = en;

    REP(i, M) {
        int a = eA[i], b = eB[i];
        L[a][b] = L[b][a] = eL[i];
        C[a][b] = C[b][a] = eC[i];
    }

    REP(i,n) {
        ll now = -1;
        while (now < inf) {
            now = dij(i, now+1);
        }
    }

    memset(totdst, 0x3f, sizeof totdst);

    REP(i,n) {
        bfs(i);
        REP(j,n) {
            if (daydst[i][j] < inf) {
                REP(k,n) {
                    MN(totdst[i][k], daydst[i][j] * S + dst[j][0][k]);
                }
            }
        }
    }

    bug(totdst[0][1], totdst[0][0]);
    bug(totdst[0][2], totdst[0][3]);
    bug(dst[0][0][2]);
    bug(dst[0][0][3]);

    vector<ll> re;
    REP(i,Q) {
        bug(i);
        int u = U[i], v = V[i];
        ll T = eT[i];
        int ver = upper_bound(ALL(stime[u]), T) - stime[u].begin() - 1;
        if (dst[u][ver][v] < inf) {
            re.pb(dst[u][ver][v]);
        }else{
            ll ans = inf;
            REP(j,n) {
                if (dst[u][ver][j] < inf) {
                    bug(j, totdst[j][v]);
                    MN(ans, S-T + totdst[j][v]);
                }
            }
            re.pb(ans);
        }
    }
  return re;
}




//#ifdef BALBIT
//signed main(){
//
//}
//#endif // BALBIT

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64980 KB Output is correct
2 Correct 32 ms 65036 KB Output is correct
3 Correct 69 ms 64988 KB Output is correct
4 Correct 25 ms 64980 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 28 ms 65004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 115468 KB Output is correct
2 Correct 671 ms 161984 KB Output is correct
3 Correct 453 ms 125172 KB Output is correct
4 Correct 815 ms 153992 KB Output is correct
5 Correct 787 ms 154544 KB Output is correct
6 Correct 32 ms 65020 KB Output is correct
7 Correct 457 ms 136052 KB Output is correct
8 Correct 516 ms 172624 KB Output is correct
9 Correct 619 ms 132700 KB Output is correct
10 Correct 868 ms 174624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64980 KB Output is correct
2 Correct 32 ms 65036 KB Output is correct
3 Correct 69 ms 64988 KB Output is correct
4 Correct 25 ms 64980 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 28 ms 65004 KB Output is correct
7 Correct 679 ms 115468 KB Output is correct
8 Correct 671 ms 161984 KB Output is correct
9 Correct 453 ms 125172 KB Output is correct
10 Correct 815 ms 153992 KB Output is correct
11 Correct 787 ms 154544 KB Output is correct
12 Correct 32 ms 65020 KB Output is correct
13 Correct 457 ms 136052 KB Output is correct
14 Correct 516 ms 172624 KB Output is correct
15 Correct 619 ms 132700 KB Output is correct
16 Correct 868 ms 174624 KB Output is correct
17 Correct 761 ms 160352 KB Output is correct
18 Correct 792 ms 160596 KB Output is correct
19 Correct 768 ms 179872 KB Output is correct
20 Correct 590 ms 157180 KB Output is correct
21 Correct 978 ms 150924 KB Output is correct
22 Correct 965 ms 150312 KB Output is correct
23 Correct 517 ms 157132 KB Output is correct
24 Correct 601 ms 151820 KB Output is correct
25 Correct 729 ms 157032 KB Output is correct
26 Correct 924 ms 147436 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64980 KB Output is correct
2 Correct 32 ms 65036 KB Output is correct
3 Correct 69 ms 64988 KB Output is correct
4 Correct 25 ms 64980 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 28 ms 65004 KB Output is correct
7 Correct 679 ms 115468 KB Output is correct
8 Correct 671 ms 161984 KB Output is correct
9 Correct 453 ms 125172 KB Output is correct
10 Correct 815 ms 153992 KB Output is correct
11 Correct 787 ms 154544 KB Output is correct
12 Correct 32 ms 65020 KB Output is correct
13 Correct 457 ms 136052 KB Output is correct
14 Correct 516 ms 172624 KB Output is correct
15 Correct 619 ms 132700 KB Output is correct
16 Correct 868 ms 174624 KB Output is correct
17 Correct 761 ms 160352 KB Output is correct
18 Correct 792 ms 160596 KB Output is correct
19 Correct 768 ms 179872 KB Output is correct
20 Correct 590 ms 157180 KB Output is correct
21 Correct 978 ms 150924 KB Output is correct
22 Correct 965 ms 150312 KB Output is correct
23 Correct 517 ms 157132 KB Output is correct
24 Correct 601 ms 151820 KB Output is correct
25 Correct 729 ms 157032 KB Output is correct
26 Correct 924 ms 147436 KB Output is correct
27 Correct 2293 ms 189244 KB Output is correct
28 Correct 2375 ms 159344 KB Output is correct
29 Correct 2568 ms 194248 KB Output is correct
30 Correct 748 ms 142064 KB Output is correct
31 Correct 2805 ms 183756 KB Output is correct
32 Correct 2806 ms 182848 KB Output is correct
33 Correct 646 ms 145228 KB Output is correct
34 Correct 2017 ms 176100 KB Output is correct
35 Correct 2733 ms 193064 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64980 KB Output is correct
2 Correct 32 ms 65036 KB Output is correct
3 Correct 69 ms 64988 KB Output is correct
4 Correct 25 ms 64980 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 28 ms 65004 KB Output is correct
7 Correct 679 ms 115468 KB Output is correct
8 Correct 671 ms 161984 KB Output is correct
9 Correct 453 ms 125172 KB Output is correct
10 Correct 815 ms 153992 KB Output is correct
11 Correct 787 ms 154544 KB Output is correct
12 Correct 32 ms 65020 KB Output is correct
13 Correct 457 ms 136052 KB Output is correct
14 Correct 516 ms 172624 KB Output is correct
15 Correct 619 ms 132700 KB Output is correct
16 Correct 868 ms 174624 KB Output is correct
17 Correct 761 ms 160352 KB Output is correct
18 Correct 792 ms 160596 KB Output is correct
19 Correct 768 ms 179872 KB Output is correct
20 Correct 590 ms 157180 KB Output is correct
21 Correct 978 ms 150924 KB Output is correct
22 Correct 965 ms 150312 KB Output is correct
23 Correct 517 ms 157132 KB Output is correct
24 Correct 601 ms 151820 KB Output is correct
25 Correct 729 ms 157032 KB Output is correct
26 Correct 924 ms 147436 KB Output is correct
27 Correct 2293 ms 189244 KB Output is correct
28 Correct 2375 ms 159344 KB Output is correct
29 Correct 2568 ms 194248 KB Output is correct
30 Correct 748 ms 142064 KB Output is correct
31 Correct 2805 ms 183756 KB Output is correct
32 Correct 2806 ms 182848 KB Output is correct
33 Correct 646 ms 145228 KB Output is correct
34 Correct 2017 ms 176100 KB Output is correct
35 Correct 2733 ms 193064 KB Output is correct
36 Execution timed out 9059 ms 217232 KB Time limit exceeded
37 Halted 0 ms 0 KB -