제출 #776349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776349		phoenix	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7039 ms	159216 KiB

dungeons

#include<bits/stdc++.h>
#include "dungeons.h"

using namespace std;
using ll = long long;

int n;
vector<int> s, p, w, l;

ll recur(int cur, ll &val) {
    if(cur == n) return val;
    if(val >= s[cur]) return recur(w[cur], val += s[cur]);
    return recur(l[cur], val += p[cur]);
}
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);
    }
};

namespace sub3 {
    const int N = 50010;
    const ll INF = 1e8;
    ll bl[N][24];
    int to[N][24];
    void build() {
        for(int lev = 0; lev < 24; lev++) {
            bl[n][lev] = INF;
            to[n][lev] = n;
            for(int i = 0; i < n; i++) {
                if(!lev) {
                    bl[i][lev] = p[i];
                    to[i][lev] = l[i];
                }
                else {
                    bl[i][lev] = bl[i][lev - 1] + bl[to[i][lev - 1]][lev - 1];
                    to[i][lev] = to[to[i][lev - 1]][lev - 1];
                }
            }
        }
    }
};

int 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;
    bool flag = 1;
    for(int i = 0; i < n; i++) 
        flag &= (s[i] == p[i]);
    sub2::build();
    if(flag) {
        Key = 0;
        return;
    }
    flag = 1;
    for(int i = 0; i < n; i++) flag &= (s[i] == s[0]);
    if(flag) {
        Key = 1;
        sub3::build();
        return;
    }
}
long long brute(int x, int z1) {
    ll z = z1;
    return recur(x, z);
}
long long simulate(int x, int z1) {
    ll z = z1;
    if(Key == 0) {
        while(x != n) {
            int next = sub2::find(x, z);
            z += sub2::sum[x] - sub2::sum[next];
            x = next;
            if(x == n) break;
            z += p[x];
            x = l[x];
        }
        return z;
    }
    if(Key == 1) {
        for(int i = 23; i >= 0; i--) {
            if(z + sub3::bl[x][i] < s[0]) {
                z += sub3::bl[x][i];
                x = sub3::to[x][i];
            }
        }
        if(x != n && z < s[0]) 
            z += p[x],
            x = l[x];
        
        return z + sub2::sum[x];
    }
    return recur(x, z);
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11