Submission #776342

#	Time	Username	Problem	Language	Result	Execution time	Memory
776342		phoenix	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	410 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] = min(bl[i][lev - 1] + bl[to[i][lev - 1]][lev - 1], INF);
                    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(z < s[0]) 
            z += p[x],
            x = l[x];
        
        return z + sub2::sum[x];
    }
    return recur(x, z);
}

// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/*
5 1000
26 26 26 26 26
44 12 31 9 41
3 2 5 4 5
3 2 5 3 3
3 22
*/

// int main() {
//     int n, q;
//     cin >> n >> q;
//     vector<int> s1(n), p1(n), w1(n), l1(n);
//     for(int &c : s1) 
//         cin >> c;
//     for(int &c : p1) 
//         cin >> c;
//     for(int &c : w1) 
//         cin >> c;
//     for(int &c : l1) 
//         cin >> c;
//     // init(n, s1, p1, w1, l1);
//     // while(q--) {
//     //     int x, y;
//     //     cin >> x >> y;
//     //     cout << simulate(x, y) << '\n';
//     // }
//     init(n, s1, p1, w1, l1);
//     while(q--) {
//         int x = rnd() % n, z = rnd() % 1000;
//         if(brute(x, z) != simulate(x, z)) {
//             cout << "WA\n";
//             cout << x << ' ' << z << '\n';
//             cout << "expexted: " << brute(x, z) << '\n';
//             cout << "found: " << simulate(x, z) << '\n';
//             return 0;
//         }
//     }
//     cout << "OK";
// }

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