Submission #551286

#	Time	Username	Problem	Language	Result	Execution time	Memory
551286		topovik	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7061 ms	567604 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 int oo = 1e18;
const ld eps = (ld)1 / oo;
const ll N = 5e4 + 100;
const ll M = 24;

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

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

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] < (1 << 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 < M; j++)
        {
            for (int i = 0; i <= n; i++)
            {
                int c = nx[pw][i][j - 1];
                nx[pw][i][j] = nx[pw][c][j - 1];
                mx[pw][i][j] = max(mx[pw][i][j - 1], mx[pw][c][j - 1] + sum[pw][i][j - 1]);
                sum[pw][i][j] = sum[pw][i][j - 1] + sum[pw][c][j - 1];
            }
        }
    }
}

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

//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;
//    }
//}
/*
1
4
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
*/

Compilation message (stderr)

dungeons.cpp:12:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const int oo = 1e18;
      |                ^~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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