제출 #625072

#제출 시각아이디문제언어결과실행 시간메모리
625072SuhaibSawalha1던전 (IOI21_dungeons)C++17
0 / 100
113 ms21912 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; vector<int> s, p, w, l; vector<long long> dis; vector<vector<int>> anc; vector<vector<long long>> sum; int n; void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { ::n = n; ::s = s; ::p = p; ::w = w; ::l = l; dis.assign(n + 1, 0); anc.assign(30, vector<int>(n + 1, -1)); sum.assign(30, vector<long long>(n + 1, 0)); dis[n] = 0; for (int i = n - 1; ~i; --i) { dis[i] = dis[w[i]] + s[i]; anc[0][i] = l[i]; sum[0][i] = p[i]; } for (int i = 1; i < 30; ++i) { for (int j = 0; j <= n; ++j) { if (~anc[i - 1][j]) { anc[i][j] = anc[i - 1][anc[i - 1][j]]; sum[i][j] = sum[i - 1][j] + sum[i - 1][anc[i - 1][j]]; sum[i][j] = min(sum[i][j], 1LL*s[0]); } } } return; } long long ans (int x, long long z) { if (x == n) { return z; } for (int i = 29; ~i; --i) { if (z + sum[i][x] < s[x]) { return ans(anc[i][x], z + sum[i][x]); } } if (z < s[x]) return ans(l[x], z+p[x]); return z + dis[x]; } long long simulate(int x, int z) { return ans(x, z); }
#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...