Submission #551325

#	Time	Username	Problem	Language	Result	Execution time	Memory
551325		topovik	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7069 ms	1789584 KiB

dungeons

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pi acos(-1)

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e18;
const ld eps = (ld)1 / oo;
const ll N = 4e5 + 1;
const ll M = 25;
const int M1 = 8;
const int M2 = 9;

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

ll sum[M][N][M2];
ll mx[M][N][M2];
int nx[M][N][M2];

void init(int n1, vector <int> s1, vector <int> p1, vector <int> w1, vector <int> l1)
{
    n = n1;
    s = s1, p = p1, w = w1, l = l1;
    for (int pw = 0; pw < M; pw++)
    {
        for (int i = 0; i < n; i++)
            if (s[i] < (1ll << pw))
        {
            nx[pw][i][0] = w[i];
            mx[pw][i][0] = -oo;
            sum[pw][i][0] = s[i];
        }
        else
        {
            nx[pw][i][0] = l[i];
            mx[pw][i][0] = -s[i];
            sum[pw][i][0] = p[i];
        }
        nx[pw][n][0] = n;
        mx[pw][n][0] = -oo;
        sum[pw][n][0] = 0;
        for (int j = 1; j < M2; j++)
        {
            for (int i = 0; i <= n; i++)
            {
                nx[pw][i][j] = nx[pw][i][j - 1];
                mx[pw][i][j] = mx[pw][i][j - 1];
                sum[pw][i][j] = sum[pw][i][j - 1];
                for (int p = 1; p < M1; p++)
                {
                    int c = nx[pw][i][j];
                    nx[pw][i][j] = nx[pw][c][j - 1];
                    mx[pw][i][j] = max(mx[pw][i][j], mx[pw][c][j - 1] + sum[pw][i][j]);
                    sum[pw][i][j] = sum[pw][i][j] + sum[pw][c][j - 1];
                }
            }
        }
    }
}

ll simulate(int x, int y1)
{
    ll y = y1;
    for (int i = 0; i < M; i++)
        if (((1ll << i) <= y && (1ll << (i + 1)) > y) || i == M - 1)
    {
        for (int j = M2 - 1; j >= 0; j--)
        {
            for (int c = 0; c < M1 && mx[i][x][j] + y < 0; c++) y += sum[i][x][j], x = nx[i][x][j];
        }
        if (x == n) return y;
        y += s[x];
        x = w[x];
    }
    return y;
}

//int main()
//{
//    srand(time(NULL));
//    ll n, q;
//    cin >> n >> q;
//    vector <int> a(n), b(n), c(n), d(n);
//    for (ll i = 0; i < n; i++) cin >> a[i];
//    for (ll i = 0; i < n; i++) cin >> b[i];
//    for (ll i = 0; i < n; i++) cin >> c[i];
//    for (ll i = 0; i < n; i++) cin >> d[i];
//    init(n, a, b, c, d);
//    while (q--)
//    {
//        ll x, z;
//        cin >> x >> z;
//        cout << simulate(x, z) << endl;
//    }
//}

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