oj.uz

Submission #777720

# Submission time Handle Problem Language Result Execution time Memory
777720 2023-07-09T13:57:37 Z phoenix Dungeons Game (IOI21_dungeons) C++17
89 / 100
 1441 ms 382204 KB 
#include<bits/stdc++.h>
#include "dungeons.h"

using namespace std;
using ll = long long;

int n;
vector<int> s, p, w, l;
const int INF = 1e7;
const int N = 50001;
namespace sub2 {
    const int N = 400010;
    vector<int> g[N];
    int anc[N][19];
    ll bl[N][19], sum[N];
    void dfs(int cur, int p) {
        anc[cur][0] = p;
        for(int i = 1; i < 19; i++) 
            anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
        if(cur != n) {
            bl[cur][0] = s[cur] + sum[cur];
            for(int i = 1; i < 19; i++) 
                bl[cur][i] = max(bl[cur][i - 1], bl[anc[cur][i - 1]][i - 1]);
        }
        for(int to : g[cur]) {
            sum[to] = sum[cur] + s[to];
            dfs(to, cur);
        } 
    }
    int find(int x, ll val) {
        val += sum[x];
        for(int i = 18; i >= 0; i--) {
            if(val >= bl[x][i]) 
                x = anc[x][i];
        }
        return x;
    }
    void build() {
        for(int i = 0; i < n; i++) {
            g[w[i]].push_back(i);
        }
        dfs(n, n);
    }
};

ll d[N];
int sm[24][24][N], to[24][24][N], mn[24][24][N];
void build() {
    for(int i = 0; i < 24; i++) {
        for(int v = 0; v <= n; v++)
            sm[i][0][v] = (s[v] < (1 << i) ? s[v] : p[v]),
            to[i][0][v] = (s[v] < (1 << i) ? w[v] : l[v]),
            mn[i][0][v] = (s[v] < (1 << i) ? INF : s[v]);
        for(int j = 1; j < 24; j++) {
            for(int v = 0; v <= n; v++) {
                sm[i][j][v] = min(sm[i][j - 1][v] + sm[i][j - 1][ to[i][j - 1][v] ], INF);
                to[i][j][v] = to[i][j - 1][ to[i][j - 1][v] ];
                mn[i][j][v] = min(mn[i][j - 1][v], mn[i][j - 1][ to[i][j - 1][v] ] - sm[i][j - 1][v]);
            }
        }
    }
}
bool Key = 1;
void init(int N, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1) {
    n = N; s = s1; p = p1; w = w1; l = l1;
    s.push_back(0); p.push_back(0);
    w.push_back(n); l.push_back(n);
    for(int i = 0; i < n; i++) Key &= (s[i] == p[i]);
    if(Key) {
        sub2::build();
        return;
    }
    d[n] = 0;
    for(int i = n - 1; i >= 0; i--)
        d[i] = s[i] + d[w[i]];
    build();

}

int level(long long x) {
    return 63 - __builtin_clzll(x);
}

ll find(int v, ll initial) {
    while(v != n && initial <= INF) {
        int lev = level(initial);
        for(int k = 23; k >= 0; k--) {
            if(initial < mn[lev][k][v] && initial + sm[lev][k][v] <= INF) {
                initial += sm[lev][k][v];
                v = to[lev][k][v];
            }
        }
        bool flag = (initial < s[v]);
        initial += (flag ? p[v] : s[v]);
        v = (flag ? l[v] : w[v]);
    }
    initial += d[v];
    return initial;
}

long long simulate(int x, int z) {
    if(Key) {
        ll res = z;
        while(x != n) {
            int next = sub2::find(x, res);
            res += sub2::sum[x] - sub2::sum[next];
            x = next;
            if(x == n) break;
            res += p[x];
            x = l[x];
        }
        return res;
    }
    return find(x, z);
}
/*
Draft
Idea for 100 pnts
Observation: if will compare the value when will defeat the monster we not used to defeat with initial value we'll see that value raised by 2
So we can divide interval [1, 1e7] by powers of 2 
=> so it'll look like: (1, 1), (2, 3), (4, 7), (8, 15), (16, 31), (32, 63) ... (2 ^ k, 2 ^ (k + 1) - 1)    
(P.S. There's log(A) = 24 segments totally.)
(*) Assume that we can jump over the monsters whose strength's segment is smaller than our's segment
=> for every such monster - i there is such k that following condition is fullfilled s[i] <= 2 ^ k <= cur_val
So after the jump we'll meet the monster whose strength was less than ours, but now we can defeat him 
so after our win our val's segment'pointer have moved by one in worst case

So totally we'll do less or equal log(A) such 'jumps'   

For jump we should precompute something for every node
sum[v][i][j] = the total value if I had started in v, and defeated only monsters whose stregth is < 2^i, and I did 2^j such moves
initial + W(v, x) >= s[x] and log2(s[x]) >= log2(initial) 

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17236 KB Output is correct
2 Correct 9 ms 17256 KB Output is correct
3 Correct 19 ms 30840 KB Output is correct
4 Correct 220 ms 351576 KB Output is correct
5 Correct 16 ms 30808 KB Output is correct
6 Correct 190 ms 351472 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9968 KB Output is correct
2 Correct 357 ms 154652 KB Output is correct
3 Correct 290 ms 166048 KB Output is correct
4 Correct 281 ms 167640 KB Output is correct
5 Correct 434 ms 136736 KB Output is correct
6 Correct 377 ms 154656 KB Output is correct
7 Correct 298 ms 164268 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 261 ms 353032 KB Output is correct
3 Correct 218 ms 353112 KB Output is correct
4 Correct 218 ms 352472 KB Output is correct
5 Correct 202 ms 352444 KB Output is correct
6 Correct 281 ms 352624 KB Output is correct
7 Correct 278 ms 352560 KB Output is correct
8 Correct 219 ms 352380 KB Output is correct
9 Correct 230 ms 352316 KB Output is correct
10 Correct 216 ms 352240 KB Output is correct
11 Correct 225 ms 352628 KB Output is correct
12 Correct 388 ms 352700 KB Output is correct
13 Correct 273 ms 352588 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 261 ms 353032 KB Output is correct
3 Correct 218 ms 353112 KB Output is correct
4 Correct 218 ms 352472 KB Output is correct
5 Correct 202 ms 352444 KB Output is correct
6 Correct 281 ms 352624 KB Output is correct
7 Correct 278 ms 352560 KB Output is correct
8 Correct 219 ms 352380 KB Output is correct
9 Correct 230 ms 352316 KB Output is correct
10 Correct 216 ms 352240 KB Output is correct
11 Correct 225 ms 352628 KB Output is correct
12 Correct 388 ms 352700 KB Output is correct
13 Correct 273 ms 352588 KB Output is correct
14 Correct 13 ms 24148 KB Output is correct
15 Correct 227 ms 352844 KB Output is correct
16 Correct 236 ms 353048 KB Output is correct
17 Correct 279 ms 352444 KB Output is correct
18 Correct 263 ms 352516 KB Output is correct
19 Correct 279 ms 352636 KB Output is correct
20 Correct 255 ms 352432 KB Output is correct
21 Correct 308 ms 352472 KB Output is correct
22 Correct 206 ms 352424 KB Output is correct
23 Correct 276 ms 352656 KB Output is correct
24 Correct 353 ms 352684 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 261 ms 353032 KB Output is correct
3 Correct 218 ms 353112 KB Output is correct
4 Correct 218 ms 352472 KB Output is correct
5 Correct 202 ms 352444 KB Output is correct
6 Correct 281 ms 352624 KB Output is correct
7 Correct 278 ms 352560 KB Output is correct
8 Correct 219 ms 352380 KB Output is correct
9 Correct 230 ms 352316 KB Output is correct
10 Correct 216 ms 352240 KB Output is correct
11 Correct 225 ms 352628 KB Output is correct
12 Correct 388 ms 352700 KB Output is correct
13 Correct 273 ms 352588 KB Output is correct
14 Correct 13 ms 24148 KB Output is correct
15 Correct 227 ms 352844 KB Output is correct
16 Correct 236 ms 353048 KB Output is correct
17 Correct 279 ms 352444 KB Output is correct
18 Correct 263 ms 352516 KB Output is correct
19 Correct 279 ms 352636 KB Output is correct
20 Correct 255 ms 352432 KB Output is correct
21 Correct 308 ms 352472 KB Output is correct
22 Correct 206 ms 352424 KB Output is correct
23 Correct 276 ms 352656 KB Output is correct
24 Correct 353 ms 352684 KB Output is correct
25 Correct 202 ms 351932 KB Output is correct
26 Correct 255 ms 353044 KB Output is correct
27 Correct 230 ms 352460 KB Output is correct
28 Correct 236 ms 352480 KB Output is correct
29 Correct 245 ms 352872 KB Output is correct
30 Correct 264 ms 352844 KB Output is correct
31 Correct 255 ms 352312 KB Output is correct
32 Correct 357 ms 352492 KB Output is correct
33 Correct 470 ms 352572 KB Output is correct
34 Correct 1441 ms 352452 KB Output is correct
35 Correct 374 ms 352508 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9968 KB Output is correct
2 Correct 357 ms 154652 KB Output is correct
3 Correct 290 ms 166048 KB Output is correct
4 Correct 281 ms 167640 KB Output is correct
5 Correct 434 ms 136736 KB Output is correct
6 Correct 377 ms 154656 KB Output is correct
7 Correct 298 ms 164268 KB Output is correct
8 Correct 14 ms 24148 KB Output is correct
9 Correct 261 ms 353032 KB Output is correct
10 Correct 218 ms 353112 KB Output is correct
11 Correct 218 ms 352472 KB Output is correct
12 Correct 202 ms 352444 KB Output is correct
13 Correct 281 ms 352624 KB Output is correct
14 Correct 278 ms 352560 KB Output is correct
15 Correct 219 ms 352380 KB Output is correct
16 Correct 230 ms 352316 KB Output is correct
17 Correct 216 ms 352240 KB Output is correct
18 Correct 225 ms 352628 KB Output is correct
19 Correct 388 ms 352700 KB Output is correct
20 Correct 273 ms 352588 KB Output is correct
21 Correct 13 ms 24148 KB Output is correct
22 Correct 227 ms 352844 KB Output is correct
23 Correct 236 ms 353048 KB Output is correct
24 Correct 279 ms 352444 KB Output is correct
25 Correct 263 ms 352516 KB Output is correct
26 Correct 279 ms 352636 KB Output is correct
27 Correct 255 ms 352432 KB Output is correct
28 Correct 308 ms 352472 KB Output is correct
29 Correct 206 ms 352424 KB Output is correct
30 Correct 276 ms 352656 KB Output is correct
31 Correct 353 ms 352684 KB Output is correct
32 Correct 202 ms 351932 KB Output is correct
33 Correct 255 ms 353044 KB Output is correct
34 Correct 230 ms 352460 KB Output is correct
35 Correct 236 ms 352480 KB Output is correct
36 Correct 245 ms 352872 KB Output is correct
37 Correct 264 ms 352844 KB Output is correct
38 Correct 255 ms 352312 KB Output is correct
39 Correct 357 ms 352492 KB Output is correct
40 Correct 470 ms 352572 KB Output is correct
41 Correct 1441 ms 352452 KB Output is correct
42 Correct 374 ms 352508 KB Output is correct
43 Correct 7 ms 17260 KB Output is correct
44 Correct 12 ms 24148 KB Output is correct
45 Incorrect 798 ms 382204 KB Output isn't correct
46 Halted 0 ms 0 KB -