oj.uz

Submission #386306

# Submission time Handle Problem Language Result Execution time Memory
386306 2021-04-06T10:31:34 Z model_code Escape Route (JOI21_escape_route) C++17
100 / 100
 2077 ms 278024 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const long long inf = 1000000000000000000;

#define N_MAX 90
#define M_MAX (N_MAX * (N_MAX - 1) / 2)
#define Q_MAX 3000000

class Path {
public:
    long long l, c, d;
    Path(): l(inf * 2), c(0), d(-inf * 2) {}
    Path(long long _l, long long _c): l(_l), c(_c), d(_c - _l) {}
};

int n, m;
long long s;
Path ps[N_MAX][N_MAX];
tuple<int, int, Path> pl[M_MAX];
long long reach[N_MAX][N_MAX];
long long from0[N_MAX][N_MAX];
long long latest_first[N_MAX][M_MAX * 2];
long long latest_second[M_MAX * 2][N_MAX];
vector<pair<long long, int>> query[N_MAX][N_MAX];
int ql[Q_MAX];
vector<long long> answer;

long long require_time(Path p, long long t) {
    t = t % s;
    if(t <= p.d) {
        return p.l;
    } else {
        return s + p.l - t;
    }
}
long long require_time_oneday(Path p, long long t) {
    if(t <= p.d) {
        return p.l;
    } else {
        return inf;
    }
}
long long require_time_oneday_reverse(Path p, long long t) {
    if(t < p.l) {
        return inf;
    } else if(t > p.c) {
        return t - p.d;
    } else {
        return p.l;
    }
}

void prepare_overday_reverse(int x) {
    vector<long long> z(n, -1);
    vector<bool> un(n, true);
    int now = x;
    z[x] = s - 1;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = -1;
        rep(i, n) {
            if(un[i]) {
                z[i] = max(z[i], nt - require_time_oneday_reverse(ps[now][i], nt));
                if(current < z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        reach[i][x] = z[i];
    }
}
void prepare_overday(int x) {
    vector<long long> z(n, inf);
    vector<bool> un(n, true);
    int now = x;
    z[x] = 0;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = inf;
        rep(i, n) {
            if(un[i]) {
                z[i] = min(z[i], nt + require_time(ps[now][i], nt));
                if(current > z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        from0[i][x] = z[i];
    }
}
void prepare_overday() {
    rep(i, n) {
        prepare_overday_reverse(i);
        prepare_overday(i);
    }
}
void prepare_oneday_reverse(int x, long long t, int w) {
    vector<long long> z(n, -1);
    vector<bool> un(n, true);
    int now = w;
    z[w] = t;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = -1;
        rep(i, n) {
            if(un[i]) {
                z[i] = max(z[i], nt - require_time_oneday_reverse(ps[now][i], nt));
                if(current < z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        latest_first[i][x] = z[i];
    }
}
void prepare_oneday(int x, long long t, int w) {
    vector<long long> z(n, inf);
    vector<bool> un(n, true);
    int now = w;
    z[w] = t;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = inf;
        rep(i, n) {
            if(un[i]) {
                z[i] = min(z[i], nt + require_time_oneday(ps[now][i], nt));
                if(current > z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        latest_second[x][i] = z[i];
    }
}
void prepare_oneday() {
    rep(i, m) {
        prepare_oneday_reverse(i * 2, get<2>(pl[i]).c, get<0>(pl[i]));
        prepare_oneday_reverse(i * 2 + 1, get<2>(pl[i]).c, get<1>(pl[i]));
        prepare_oneday(i * 2, get<2>(pl[i]).c, get<0>(pl[i]));
        prepare_oneday(i * 2 + 1, get<2>(pl[i]).c, get<1>(pl[i]));
    }
}
void prepare() {
    prepare_overday();
    prepare_oneday();
}

void solve_overday(int u, int v) {
    vector<pair<long long, long long>> w;
    rep(i, n) {
        if(reach[u][i] >= 0) {
            w.push_back(make_pair(reach[u][i], from0[v][i]));
        }
    }
    for(auto i: query[u][v]) {
        w.push_back(make_pair(i.first, i.second - inf));
    }
    sort(w.begin(), w.end(), greater<pair<long long, long long>>());
    long long now = inf;
    for(auto i: w) {
        if(i.second < 0) {
            answer[i.second + inf] = min(answer[i.second + inf], s - i.first + now);
        } else {
            now = min(now, i.second);
        }
    }
    for(auto i: w) {
        if(i.second < 0) {
            answer[i.second + inf] = min(answer[i.second + inf], s * 2 - i.first + now);
        }
    }
}
void solve_oneday(int u) {
    vector<pair<long long, long long>> w;
    rep(i, m * 2) {
        if(latest_first[u][i] >= 0) {
            w.push_back(make_pair(latest_first[u][i], i));
        }
    }
    rep(i, n) {
        for(auto j: query[u][i]) {
            w.push_back(make_pair(j.first, j.second - inf));
        }
    }
    sort(w.begin(), w.end(), greater<pair<long long, long long>>());
    vector<long long> now(n, inf);
    for(auto i: w) {
        if(i.second < 0) {
            int idx = i.second + inf;
            answer[idx] = min(answer[idx], now[ql[idx]]);
        } else {
            rep(j, n) {
                now[j] = min(now[j], latest_second[i.second][j] - i.first);
            }
        }
    }
    for(auto i: w) {
        if(i.second < 0) {
            int idx = i.second + inf;
            answer[idx] = min(answer[idx], s - i.first + now[ql[idx]]);
        }
    }
}
void solve(int q) {
    answer.resize(q, inf);
    rep(i, n) {
        rep(j, n) {
            if(i != j) {
                solve_overday(i, j);
            }
        }
    }
    rep(i, n) {
        solve_oneday(i);
    }
}

vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, vector<int> A, vector<int> B,
    vector<long long> L, vector<long long> C, vector<int> U,
    vector<int> V, vector<long long> T) {
    n = N;
    m = M;
    s = S;
    rep(i, m) {
        Path p(L[i], C[i]);
        ps[A[i]][B[i]] = p;
        ps[B[i]][A[i]] = p;
        pl[i] = make_tuple(A[i], B[i], p);
    }
    rep(i, Q) {
        query[U[i]][V[i]].push_back(make_pair(T[i], i));
        ql[i] = V[i];
    }
    prepare();
    solve(Q);
    return answer;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65644 KB Output is correct
2 Correct 45 ms 65644 KB Output is correct
3 Correct 71 ms 65644 KB Output is correct
4 Correct 37 ms 65644 KB Output is correct
5 Correct 55 ms 65644 KB Output is correct
6 Correct 38 ms 65644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1476 ms 249324 KB Output is correct
2 Correct 1498 ms 262820 KB Output is correct
3 Correct 1485 ms 278024 KB Output is correct
4 Correct 1572 ms 266624 KB Output is correct
5 Correct 1610 ms 267408 KB Output is correct
6 Correct 46 ms 65516 KB Output is correct
7 Correct 1530 ms 240796 KB Output is correct
8 Correct 1573 ms 277852 KB Output is correct
9 Correct 1507 ms 240816 KB Output is correct
10 Correct 1573 ms 266216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65644 KB Output is correct
2 Correct 45 ms 65644 KB Output is correct
3 Correct 71 ms 65644 KB Output is correct
4 Correct 37 ms 65644 KB Output is correct
5 Correct 55 ms 65644 KB Output is correct
6 Correct 38 ms 65644 KB Output is correct
7 Correct 1476 ms 249324 KB Output is correct
8 Correct 1498 ms 262820 KB Output is correct
9 Correct 1485 ms 278024 KB Output is correct
10 Correct 1572 ms 266624 KB Output is correct
11 Correct 1610 ms 267408 KB Output is correct
12 Correct 46 ms 65516 KB Output is correct
13 Correct 1530 ms 240796 KB Output is correct
14 Correct 1573 ms 277852 KB Output is correct
15 Correct 1507 ms 240816 KB Output is correct
16 Correct 1573 ms 266216 KB Output is correct
17 Correct 1241 ms 252368 KB Output is correct
18 Correct 1249 ms 250308 KB Output is correct
19 Correct 1355 ms 272452 KB Output is correct
20 Correct 1246 ms 205816 KB Output is correct
21 Correct 1333 ms 213968 KB Output is correct
22 Correct 1350 ms 214080 KB Output is correct
23 Correct 1284 ms 201724 KB Output is correct
24 Correct 1333 ms 224592 KB Output is correct
25 Correct 1238 ms 189868 KB Output is correct
26 Correct 1368 ms 213588 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65644 KB Output is correct
2 Correct 45 ms 65644 KB Output is correct
3 Correct 71 ms 65644 KB Output is correct
4 Correct 37 ms 65644 KB Output is correct
5 Correct 55 ms 65644 KB Output is correct
6 Correct 38 ms 65644 KB Output is correct
7 Correct 1476 ms 249324 KB Output is correct
8 Correct 1498 ms 262820 KB Output is correct
9 Correct 1485 ms 278024 KB Output is correct
10 Correct 1572 ms 266624 KB Output is correct
11 Correct 1610 ms 267408 KB Output is correct
12 Correct 46 ms 65516 KB Output is correct
13 Correct 1530 ms 240796 KB Output is correct
14 Correct 1573 ms 277852 KB Output is correct
15 Correct 1507 ms 240816 KB Output is correct
16 Correct 1573 ms 266216 KB Output is correct
17 Correct 1241 ms 252368 KB Output is correct
18 Correct 1249 ms 250308 KB Output is correct
19 Correct 1355 ms 272452 KB Output is correct
20 Correct 1246 ms 205816 KB Output is correct
21 Correct 1333 ms 213968 KB Output is correct
22 Correct 1350 ms 214080 KB Output is correct
23 Correct 1284 ms 201724 KB Output is correct
24 Correct 1333 ms 224592 KB Output is correct
25 Correct 1238 ms 189868 KB Output is correct
26 Correct 1368 ms 213588 KB Output is correct
27 Correct 1339 ms 211716 KB Output is correct
28 Correct 1343 ms 213980 KB Output is correct
29 Correct 1475 ms 226628 KB Output is correct
30 Correct 1396 ms 209548 KB Output is correct
31 Correct 1449 ms 223064 KB Output is correct
32 Correct 1424 ms 223200 KB Output is correct
33 Correct 1310 ms 232168 KB Output is correct
34 Correct 1344 ms 199008 KB Output is correct
35 Correct 1505 ms 223644 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65644 KB Output is correct
2 Correct 45 ms 65644 KB Output is correct
3 Correct 71 ms 65644 KB Output is correct
4 Correct 37 ms 65644 KB Output is correct
5 Correct 55 ms 65644 KB Output is correct
6 Correct 38 ms 65644 KB Output is correct
7 Correct 1476 ms 249324 KB Output is correct
8 Correct 1498 ms 262820 KB Output is correct
9 Correct 1485 ms 278024 KB Output is correct
10 Correct 1572 ms 266624 KB Output is correct
11 Correct 1610 ms 267408 KB Output is correct
12 Correct 46 ms 65516 KB Output is correct
13 Correct 1530 ms 240796 KB Output is correct
14 Correct 1573 ms 277852 KB Output is correct
15 Correct 1507 ms 240816 KB Output is correct
16 Correct 1573 ms 266216 KB Output is correct
17 Correct 1241 ms 252368 KB Output is correct
18 Correct 1249 ms 250308 KB Output is correct
19 Correct 1355 ms 272452 KB Output is correct
20 Correct 1246 ms 205816 KB Output is correct
21 Correct 1333 ms 213968 KB Output is correct
22 Correct 1350 ms 214080 KB Output is correct
23 Correct 1284 ms 201724 KB Output is correct
24 Correct 1333 ms 224592 KB Output is correct
25 Correct 1238 ms 189868 KB Output is correct
26 Correct 1368 ms 213588 KB Output is correct
27 Correct 1339 ms 211716 KB Output is correct
28 Correct 1343 ms 213980 KB Output is correct
29 Correct 1475 ms 226628 KB Output is correct
30 Correct 1396 ms 209548 KB Output is correct
31 Correct 1449 ms 223064 KB Output is correct
32 Correct 1424 ms 223200 KB Output is correct
33 Correct 1310 ms 232168 KB Output is correct
34 Correct 1344 ms 199008 KB Output is correct
35 Correct 1505 ms 223644 KB Output is correct
36 Correct 2015 ms 225980 KB Output is correct
37 Correct 1964 ms 230300 KB Output is correct
38 Correct 1955 ms 215612 KB Output is correct
39 Correct 2067 ms 237592 KB Output is correct
40 Correct 2077 ms 238292 KB Output is correct
41 Correct 1298 ms 240516 KB Output is correct
42 Correct 1967 ms 213948 KB Output is correct
43 Correct 1978 ms 218088 KB Output is correct