제출 #465350

#제출 시각아이디문제언어결과실행 시간메모리
465350Peti던전 (IOI21_dungeons)C++17
63 / 100
3401 ms2097156 KiB
#include <bits/stdc++.h> #include "dungeons.h" using namespace std; const long long INF = (long long)1e18; const int logn = 25; struct adat{ int ind; long long legk, ossz; adat() {} adat(int ind, long long legk, long long ossz) : ind(ind), legk(legk), ossz(ossz) {} }; inline adat merge(adat a, adat b){ return adat(b.ind, min(a.legk, b.legk-a.ossz), a.ossz+b.ossz); } vector<vector<vector<adat>>> st; vector<int> s, p, w, l; int n; void calcST(vector<vector<adat>> &v, int k){ v.resize(n, vector<adat>(logn)); for(int i = 0; i < n; i++){ if(s[i] <= k) v[i][0] = adat(w[i], INF, s[i]); else v[i][0] = adat(l[i], s[i], p[i]); } for(int j = 1; j < logn; j++) for(int i = 0; i < n; i++) v[i][j] = merge(v[i][j-1], v[v[i][j-1].ind][j-1]); } void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) { n = N; s = S; p = P; w = W; l = L; s.push_back(0); p.push_back(0); w.push_back(n); l.push_back(n); ++n; //int m = logn/(1<<bont)+1; st.resize(logn); for(int i = 0; i < logn; i++) calcST(st[i], 1ll<<i); return; } long long simulate(int x, int z) { int y = 0; long long ert = z; while (x != n-1) { while (y+1 < logn && 1ll<<(y+1) <= ert) ++y; for(int i = logn-1; i >= 0; i--){ if(st[y][x][i].legk > ert){ //cout<<"move: "<<i<<' '<<st[y][x][i].ind<<' '<<st[y][x][i].legk<<'\n'; ert += st[y][x][i].ossz; x = st[y][x][i].ind; } } //ert += st[y][x][0].ossz; //x = st[y][x][0].ind; //cout<<"h: "<<x<<' '<<ert<<'\n'; ert += (long long)s[x]; x = w[x]; } return ert; }
#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...