Submission #776341

#	Time	Username	Problem	Language	Result	Execution time	Memory
776341		phoenix	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	426 ms	167592 KiB

dungeons

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

using namespace std;
using ll = long long;

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

bool flag = 0;
ll recur(int cur, ll &val) {
    if(cur == n) return val;
    if(val >= s[cur]) {
        flag = 1;
        return recur(w[cur], val += s[cur]);
    }
    if(flag) return -1;
    flag = 0;
    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);
        }
        sum[0] = 0;
        dfs(n, n);
        for(int i = 0; i < n; i++) g[i].clear();
    }
};
namespace sub3 {
    const int N = 50010;
    const ll INF = 1e9;
    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;
    flag = 0;
    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
*/
vector<int> s1(n), p1(n), w1(n), l1(n);
int q;
void gen() {
    n = 100; q = 1000;
    s1.resize(n);
    s1[0] = rnd() % 1000000;
    for(int i = 0; i < n; i++) 
        s1[i] = s1[0];
    p1.resize(n);
    for(int i = 0; i < n; i++) 
        p1[i] = rnd() % 1000000;
    w1.resize(n);
    for(int i = 0; i < n; i++) 
        w1[i] = rnd() % (n - i) + i + 1;
    l1.resize(n);
    for(int i = 0; i < n; i++) 
        l1[i] = rnd() % n;
}

// int main() {
    
    // cin >> n >> q;
    // s1.resize(n);
    // p1.resize(n);
    // w1.resize(n);
    // l1.resize(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';
    // }
    // for(int t = 0; t < 100; t++) {
    //     gen();
    //     init(n, s1, p1, w1, l1);
    //     while(q--) {
    //         int x = rnd() % n, z = rnd() % 1000;
    //         // if(brute(x, z) == -1) {
    //         //     cout << "Wrong observation :(\n";
    //         //     cout << n << '\n';
    //         //     for(int c : s1) cout << c << ' ';
    //         //     cout << '\n';
    //         //     for(int c : p1) cout << c << ' ';
    //         //     cout << '\n';
    //         //     for(int c : w1) cout << c << ' ';
    //         //     cout << '\n';
    //         //     for(int c : l1) cout << c << ' ';
    //         //     cout << '\n';
    //         //     cout << x << ' ' << z;
    //         //     exit(0);
    //         // }
    //         // 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: 0 / 11
• Subtask 2: 26 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11