This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 400005;
int N;
pair<pair<int,int>,int> lca[nmax][19];
vector<int>L_cringe;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = n;
for(auto &it : w) ++it;
for(auto &it : l) ++it;
L_cringe = l;
for(int i=1;i<=n;i++){
lca[i][0].fr.fr = s[i - 1];
lca[i][0].fr.sc = -s[i - 1];
lca[i][0].sc = w[i - 1];
}
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
lca[i][j].sc = lca[lca[i][j-1].sc][j-1].sc;
lca[i][j].fr.fr = lca[i][j-1].fr.fr + lca[lca[i][j-1].sc][j-1].fr.fr;
lca[i][j].fr.sc = min(lca[i][j-1].fr.sc, lca[i][j-1].fr.fr + lca[lca[i][j-1].sc][j-1].fr.sc);
}
}
return;
}
long long simulate(int x, int z) {
int curr = z;
++x;
while(x != N + 1){
for(int j=18;j>=0;j--){
if(lca[x][j].sc != 0 && lca[x][j].fr.sc + curr >= 0){
curr += lca[x][j].fr.fr;
x = lca[x][j].sc;
}
}
if(x != N + 1){
curr += lca[x][0].fr.fr;
x = L_cringe[x - 1];
}
}
return curr;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |