제출 #1196322

#제출 시각아이디문제언어결과실행 시간메모리
1196322Amr던전 (IOI21_dungeons)C++20
24 / 100
7105 ms308064 KiB
#include "dungeons.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define sz size() #define F first #define S second typedef long long ll; const int Log = 23; const int N = 4e5+3; ll sp[N][Log], spmn[N][Log], spsum[N][Log], splst[N][Log]; ll m; vector<int> S , P , W , L; void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) { m = n; S = s, P = p, W = w, L = l; for(int i = 0; i < n; i++) spmn[i][0] = s[i], spsum[i][0] = p[i], splst[i][0] = p[i],sp[i][0] = l[i]; spmn[n][0] = -1, splst[n][0] = 0, spsum[n][0] = 0,sp[n][0] = n; for(int j = 1; j < Log; j++) { for(int i = 0; i <= n; i++) { spmn[i][j] = min(spmn[i][j-1],spmn[sp[i][j-1]][j-1]); splst[i][j] = splst[sp[i][j-1]][j-1]; spsum[i][j] = spsum[i][j-1] + spsum[sp[i][j-1]][j-1]; sp[i][j] = sp[sp[i][j-1]][j-1]; } } //cout << splst[2][2] << endl; } long long simulate(int x, int z) { ll curp = x, curv = z; ll cnt = 5; while(curp!=m) { if(curv<S[curp]) { for(int i = Log-1; i >= 0; i--) { if(curv+spsum[curp][i]-splst[curp][i]<spmn[curp][i]) { curv += spsum[curp][i]; curp = sp[curp][i]; } } } else { curv += S[curp]; curp = W[curp]; } // cout << curv << " " <<curp << endl; } return curv; }
#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...