Submission #777720

#	Time	Username	Problem	Language	Result	Execution time	Memory
777720		phoenix	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	1441 ms	382204 KiB

dungeons

#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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11