Submission #1053171

#TimeUsernameProblemLanguageResultExecution timeMemory
1053171ZicrusDungeons Game (IOI21_dungeons)C++17
0 / 100
7078 ms604 KiB
#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++) {
      |                        ~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...