Submission #815390

#	Time	Username	Problem	Language	Result	Execution time	Memory
815390		eltu0815	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3212 ms	527176 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int N;
int s[400000], w[400000];
int pos[6][400001][18], mn[6][400001][18], sum[6][400001][18];
ll dp[400001];

void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    N = n;
    for(int i = 0; i < n; ++i) s[i] = S[i], w[i] = W[i];
    for(int j = 0; j < 6; ++j) {
        for(int i = 0; i < N; ++i) {
            pos[j][i][0] = (1 << 4 * j) <= S[i] ? L[i] : W[i];
            sum[j][i][0] = (1 << 4 * j) <= S[i] ? P[i] : S[i];
            mn[j][i][0] = (1 << 4 * j) <= S[i] ? S[i] : (int)(1e9);
        }
        pos[j][N][0] = N, sum[j][N][0] = mn[j][N][0] = (int)(1e9);
    }
    for(int k = 0; k < 6; ++k) for(int j = 1; j <= 17; ++j) {
        for(int i = 0; i <= N; ++i) {
            pos[k][i][j] = pos[k][pos[k][i][j - 1]][j - 1];
            sum[k][i][j] = sum[k][pos[k][i][j - 1]][j - 1] + sum[k][i][j - 1];
            mn[k][i][j] = min(mn[k][i][j - 1], mn[k][pos[k][i][j - 1]][j - 1] - sum[k][i][j - 1]);
            
            sum[k][i][j] = min(sum[k][i][j], (int)(1e9));
            mn[k][i][j] = max(mn[k][i][j], 0);
        }
    }
    
    for(int i = n - 1; i >= 0; --i) dp[i] = dp[W[i]] + S[i];
	return;
}
 
long long simulate(int x, int z) {
    ll ans = z;
    for(int k = 0; k < 6; ++k) {
        while(ans < (1 << 4 * k + 4)) {
            for(int j = 17; j >= 0; --j) {
                if(pos[k][x][j] != N && sum[k][x][j] + ans < (1 << 4 * k + 4) && mn[k][x][j] > ans) {
                    ans += sum[k][x][j], x = pos[k][x][j];
                }
            }
            if(s[x] <= ans) ans += s[x], x = w[x];
            else if(ans < (1 << 4 * k + 4)) ans += sum[k][x][0], x = pos[k][x][0];
            if(x == N) return ans;
        }
    }
	return ans + dp[x];
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:41:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |         while(ans < (1 << 4 * k + 4)) {
      |                           ~~~~~~^~~
dungeons.cpp:43:74: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 |                 if(pos[k][x][j] != N && sum[k][x][j] + ans < (1 << 4 * k + 4) && mn[k][x][j] > ans) {
      |                                                                    ~~~~~~^~~
dungeons.cpp:48:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |             else if(ans < (1 << 4 * k + 4)) ans += sum[k][x][0], x = pos[k][x][0];
      |                                 ~~~~~~^~~

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