Submission #1053171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053171		Zicrus	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7078 ms	604 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;

typedef long long ll;

int n;
vector<int> p, w, l;
int s;
vector<vector<pair<ll, ll>>> jmp;
vector<ll> dp;

void init(int n1, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1) {
    n = n1; s = s1[0]; p = p1; w = w1; l = l1;
    jmp = vector<vector<pair<ll, ll>>>(n, vector<pair<ll, ll>>(20));
    for (int i = 0; i < n; i++) {
        jmp[i][0] = {p[i], l[i]};
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            jmp[i][j] = {jmp[jmp[i][j-1].second][j-1].first + jmp[i][j-1].first,
                         jmp[jmp[i][j-1].second][j-1].second};
        }
    }
    dp = vector<ll>(n+1);
    dp[n] = 0;
    for (int i = n-1; i >= 0; i--) {
        dp[i] = s + dp[w[i]];
    }
}

ll simulate(int x1, int z1) {
	ll i = x1, z = z1;
    for (int j = 20-1; j >= 0; j++) {
        if (z + jmp[i][j].first < s) {
            z += jmp[i][j].first;
            i += jmp[i][j].second;
        }
    }
    if (z < s) {
        z += jmp[i][0].first;
        i += jmp[i][0].second;
    }
    z += dp[i];
    return z;
}

Compilation message (stderr)

dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:34:5: warning: iteration 2147483628 invokes undefined behavior [-Waggressive-loop-optimizations]
   34 |     for (int j = 20-1; j >= 0; j++) {
      |     ^~~
dungeons.cpp:34:26: note: within this loop
   34 |     for (int j = 20-1; j >= 0; j++) {
      |                        ~~^~~~

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