oj.uz

Submission #439872

# Submission time Handle Problem Language Result Execution time Memory
439872 2021-07-01T04:26:57 Z 최서현(#7501) Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 464 ms 172992 KB 
#include "jumps.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <iostream>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

int N;
int X[202020];
vector<int> H;
pii ind[404040];
vector<int> gph[202020];
int dep[202020];
int cnt = 0;
piii sp[202020][20][3];

int qr(int l, int r)
{
    pii ret = {-1, -1};
    for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
    {
        if(x & 1) ret = max(ret, ind[x++]);
        if(y & 1) ret = max(ret, ind[--y]);
    }
    return ret.ss;
}

int dfs(int l, int r, int d, int p, bool f)
{
    int nd = cnt++;
    dep[nd] = d;

    if(f)
    {
        sp[nd][0][0] = {p, {0, 1}};
        sp[nd][0][1] = {p, {0, 1}};
        sp[nd][0][2] = {p, {1, 0}};
    }
    else
    {
        sp[nd][0][0] = {p, {0, 2}};
        sp[nd][0][1] = {p, {1, 0}};
        sp[nd][0][2] = {p, {0, 2}};
    }

    if(l == r) return nd;

    int mid = qr(l, r);
    X[mid] = cnt;
    gph[nd].push_back(dfs(l, mid, d + 1, nd, true));
    gph[nd].push_back(dfs(mid + 1, r, d + 1, nd, false));
    return nd;
}

void init(int N, vector<int> H)
{
    ::N = N;
    ::H = H;
//    vector<int> S;
//    for(int i = 0; i < N; ++i)
//    {
//        while(S.size() && H[S.back()] < H[i]) L[S.back()].[i], S.pop_back();
//        S.push_back(i);
//    }

    for(int i = 0; i < N; ++i) ind[i + N] = {H[i], i};
    for(int i = N - 1; i >= 1; --i) ind[i] = max(ind[i << 1], ind[i << 1 | 1]);
    dfs(0, N, 0, 0, true);

    for(int i = 1; i < 20; ++i)
    {
        for(int j = 0; j < cnt; ++j)
        {
            int t = sp[j][i - 1][0].ff;
            int k = sp[t][i - 1][0].ff;
            sp[j][i][0] = { k, { sp[t][i - 1][0].ee + sp[j][i - 1][sp[t][i - 1][0].rr].ee, sp[j][i - 1][sp[t][i - 1][0].rr].rr } };
            sp[j][i][1] = { k, { sp[t][i - 1][1].ee + sp[j][i - 1][sp[t][i - 1][1].rr].ee, sp[j][i - 1][sp[t][i - 1][1].rr].rr } };
            sp[j][i][2] = { k, { sp[t][i - 1][2].ee + sp[j][i - 1][sp[t][i - 1][2].rr].ee, sp[j][i - 1][sp[t][i - 1][2].rr].rr } };
        }
    }
}

int minimum_jumps(int A, int B, int C, int D)
{
    int x = X[A], y = X[C];
    vector<pii> ret(3);
    ret[0] = {0, 0};
    ret[1] = {0, 1};
    ret[2] = {0, 2};
    for(int i = 19; i >= 0; --i) if(dep[x] - (1 << i) >= dep[y])
    {
        vector<pii> _ret(3);
        for(int j = 0; j < 3; ++j)
        {
            _ret[j] = { sp[x][i][j].ee + ret[sp[x][i][j].rr].ff, ret[sp[x][i][j].rr].ss };
        }
        ret = _ret;
        x = sp[x][i][0].ff;
    }
//    #ifdef DEBUG
//        cout << endl;
//        cout << "ret" << endl;
//        for(auto i : ret) cout << i.ff << ' ' << i.ss << endl;
//        cout << endl;
//    #endif
    if(x != y) return -1;
    else return ret[2].ff + (ret[2].ss == 1 ? 1 : 0);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 5064 KB Output is correct
3 Incorrect 290 ms 172992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5064 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 4 ms 5064 KB Output is correct
4 Incorrect 464 ms 140300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5064 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 4 ms 5064 KB Output is correct
4 Incorrect 464 ms 140300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 5064 KB Output is correct
3 Incorrect 290 ms 172992 KB Output isn't correct
4 Halted 0 ms 0 KB -