Submission #1246136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246136		sano	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	59 ms	24240 KiB

dungeons

//#include "parks.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#include <variant>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

ll n;
vec<ll> s, p, w, l;
vec<ll> dist;
vec<vec<ll>> skok;
vec<vec<ll>> sila;
void init(int n1, vec<int>s1, vec<int>p1, vec<int>w1, vec<int>l1) {
    s.clear();
    p.clear();
    w.clear();
    l.clear();
    dist.clear();
    skok.clear();
    sila.clear();
    n = n1;
    For(i, n1) {
        s.push_back(s1[i]);
        p.push_back(p1[i]);
        w.push_back(w1[i]);
        l.push_back(l1[i]);
    }
    dist.resize(n + 1);
    dist[n] = 0;
    rfor(i, n - 1) {
        dist[i] = dist[w[i]] + s[i];
    }
    skok.resize(n + 1, vec<ll>(20));
    sila.resize(n + 1, vec<ll>(20));
    For(i, n) {
        skok[i][0] = l[i];
        sila[i][0] = p[i];
    }
    skok[n][0] = n;
    sila[n][0] = 0;
    ffor(i, 1, 20) {
        For(j, n + 1) {
            skok[j][i] = skok[skok[j][i - 1]][i - 1];
            sila[j][i] = sila[j][i - 1] + sila[skok[j][i - 1]][i - 1];
        }
    }
    return;
}

void chod(ll& x, ll& z) {
    ll S = s[0];
    if (z >= S) {
        return;
    }
    rfor(i, 19) {
        if (z + sila[x][i] < S) {
            z += sila[x][i];
            x = skok[x][i];
        }
    }
    z += sila[x][0];
    x = skok[x][0];
    return;
}

void najdi_n(ll& x, ll& z) {
    ll S = s[0];
    if (skok[x][19] != n) {
        x = n, z = NEK;
    }
    if (z >= S) {
        return;
    }
    rfor(i, 19) {
        if (skok[x][i] !=  n) {
            z += sila[x][i];
            x = skok[x][i];
            
        }
    }
    z += sila[x][0];
    x = skok[x][0];
    return;
}

ll simulate(int x1, int z1) {
    ll x = x1, z = z1;
    ll S = s[0];
    ll x2 = x, z2 = z;
    najdi_n(x2, z2);
    chod(x, z);
    if (z2 < z) {
        return z2;
    }
    z += dist[x];
    return z;
}

ll simulate2(int x1, int z1) {
    ll x = x1, z = z1;
    while (x != n) {
        if (s[x] > z) {
            z += p[x];
            x = l[x];
        }
        else {
            z += s[x];
            x = w[x];
        }
    }
    return z;
}



void generovanie() {
    int n1, q;
    //cin >> n1; cin >> q;
    int cnt = 0;
    while (1) {
        n1 = rand() % 10 + 1;
        q = rand() % 5 + 1;
        vec<int> s1(n1), p1(n1), w1(n1), l1(n1);
        int S = rand() % 20 + 1;
        For(i, n1) {
            //cin >> s1[i];
            s1[i] = S;
        }
        For(i, n1) {
            //cin >> p1[i];
            p1[i] = rand() % 20 + 1;
        }
        For(i, n1) {
            //cin >> w1[i];
            w1[i] = i + 1 + rand() % (n1 - i);
        }
        For(i, n1) {
            //cin >> l1[i];
            l1[i] = rand() % (n1 + 1);
        }
        init(n1, s1, p1, w1, l1);
        For(i, q) {
            int a, b;
            //cin >> a >> b;
            a = rand() % n1, b = rand() % 25;
            ll odp1 = simulate(a, b);
            ll odp2 = simulate2(a, b);
            cout << odp1 << '\n';
            if (odp1 != odp2) {
                odp1 = simulate(a, b);
                odp2 = simulate2(a, b);
                return;
            }
        }
    }
    return;
}


void normalne() {
    int n1, q;
    cin >> n1; cin >> q;
    vec<int> s1(n1), p1(n1), w1(n1), l1(n1);
    int S = rand() % 20 + 1;
    For(i, n1) {
        cin >> s1[i];
    }
    For(i, n1) {
        cin >> p1[i];
    }
    For(i, n1) {
        cin >> w1[i];
    }
    For(i, n1) {
        cin >> l1[i];
    }
    init(n1, s1, p1, w1, l1);
    For(i, q) {
        int a, b;
        cin >> a >> b;
        ll odp1 = simulate(a, b);
        cout << odp1 << '\n';
    }
    return;
}
/*

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    normalne();
    return 0;
}*/

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