제출 #834371

#제출 시각아이디문제언어결과실행 시간메모리
834371Abrar_Al_Samit던전 (IOI21_dungeons)C++17
13 / 100
111 ms35148 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; const int nax = 4e5 + 3; int n; vector<int>s, p, w, l; long long sum_toN[nax]; vector<int>g[nax]; void dfs(int v, long long sum = 0) { if(v < n) sum += s[v]; sum_toN[v] = sum; for(int u : g[v]) { dfs(u, sum); } } const int lg = 24; long long sp[nax][lg], agg[nax][lg]; 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; for(int i=0; i<n; ++i) { g[w[i]].push_back(i); } dfs(n); for(int i=0; i<n; ++i) { sp[i][0] = l[i]; agg[i][0] = p[i]; } sp[n][0] = n; for(int j=1; j<lg; ++j) { for(int i=0; i<=n; ++i) { sp[i][j] = sp[sp[i][j-1]][j-1]; agg[i][j] = agg[i][j-1] + agg[sp[i][j-1]][j-1]; } } } const int anax = 1e7; long long simulate(int x, int z) { long long cz = z; for(int j=lg-1; j>=0; --j) { if(cz + agg[x][j] < s[0] && sp[x][j] < n) { cz += agg[x][j]; x = sp[x][j]; } } if(cz < s[0]) { cz += agg[x][0]; x = sp[x][0]; } cz += sum_toN[x]; return cz; }
#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...