#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
#include "dungeons.h"
vector<ll> s, p, w, l;
ll n;
ll win[(ll)(5e4 + 7)], comp[(ll)(5e4 + 7)];
vector<ll> d[(ll)(5e4 + 7)], d2[(ll)(5e4 + 7)];
void find_comp(ll v, ll step){
comp[v] = step;
for(auto i: d[v]){
if(!comp[i])
find_comp(i, step);
}
}
vector<ll> ord;
ll used[(ll)(5e4 + 7)], par[(ll)(5e4 + 7)], tot[(ll)(5e4 + 7)];
pair<ll, ll> t[(ll)(5e4 + 7)][22];
bool loop[(ll)(5e4 + 7)];
void find_loop(ll v, ll prev){
used[v] = 1;
par[v] = prev;
for(auto i: d2[v]){
if(used[i] == 1){
ll cur = v;
while(cur != -1 && cur != i){
ord.push_back(cur);
cur = par[cur];
}
ord.push_back(i);
}
else if(!used[i]){
find_loop(i, v);
}
}
used[v] = 2;
}
ll par_pos[(ll)(5e4 + 7)];
vector<ll> pref[(ll)(5e4 + 7)];
vector<ll> loops[(ll)(5e4 + 7)];
void build(ll v, ll par){
t[v][0].first = par;
if(par != 0)
t[v][0].second = p[v];
for(ll i = 1; i < 20; i++){
t[v][i].first = t[t[v][i - 1].first][i - 1].first;
t[v][i].second = t[v][i - 1].second + t[t[v][i - 1].first][i - 1].second;
}
for(auto i: d[v]){
if(i != par && !loop[i])
build(i, v);
}
}
void init(int n0, std::vector<int> s0, std::vector<int> p0, std::vector<int> w0, std::vector<int> l0){
n = n0;
s.clear();
p.clear();
w.clear();
l.clear();
for(int i = 0; i <= n; i++){
pref[i].clear();
loops[i].clear();
d[i].clear();
d2[i].clear();
for(int j = 0; j < 20; j++)
t[i][j].first = t[i][j].second = 0;
par_pos[i] = used[i] = par[i] = tot[i] = loop[i] = win[i] = comp[i] = 0;
}
s.resize(n + 1);
p.resize(n + 1);
w.resize(n + 1);
l.resize(n + 1);
for(ll i = 1; i <= n; i++){
s[i] = s0[i - 1], p[i] = p0[i - 1], w[i] = w0[i - 1], l[i] = l0[i - 1];
w[i]++, l[i]++;
}
for(ll i = n; i >= 1; i--)
win[i] = win[w[i]] + (ll)s[i];
for(ll i = 1; i <= n; i++){
d[i].push_back(l[i]);
d[l[i]].push_back(i);
}
ll step = 0;
for(ll i = 1; i <= n; i++)
if(!comp[i])
find_comp(i, ++step);
vector<ll> st(n + 1), in(n + 1);
for(int i = 1; i <= n; i++)
in[l[i]]++;
for(int i = 1; i <= n; i++){
if(st[comp[i]] == 0 || in[i] == 0)
st[comp[i]] = i;
}
for(ll i = 1; i <= n; i++){
d2[i].push_back(l[i]);
}
vector<bool> used_comp(step + 1);
for(ll i = 1; i <= n; i++){
if(used_comp[comp[i]])
continue;
used_comp[comp[i]] = true;
ord.clear();
find_loop(st[comp[i]], -1);
reverse(ord.begin(), ord.end());
loops[comp[i]] = ord;
for(auto j: ord)
loop[j] = true;
// cout << i << ' ' << (ll)(ord.size()) << endl;
// for(auto j: ord)
// cout << j << ' ';
// cout << endl;
for(ll j = 0; j < (ll)(ord.size()); j++){
build(ord[j], 0);
par_pos[ord[j]] = j;
}
for(auto j: ord)
tot[comp[i]] += p[j];
pref[comp[i]].resize((ll)(ord.size()));
for(ll j = 0; j < (ll)(ord.size()); j++)
pref[comp[i]][j] = (j == 0 ? 0 : pref[comp[i]][j - 1]) + p[ord[j]];
for(auto j: ord)
loop[j] = false;
}
}
ll get_sum(ll c, ll pos, ll mid){
if(mid == 0 || pref[c].empty())
return 0;
ll cnt = 0;
if(pos + mid - 1 < (ll)(pref[c].size())){
cnt = pref[c][pos + mid - 1];
if(pos != 0)
cnt -= pref[c][pos - 1];
}
else{
ll can = (ll)(pref[c].size()) - pos;
cnt = pref[c].back();
if(pos != 0)
cnt -= pref[c][pos - 1];
ll need = mid - can;
cnt += pref[c][need - 1];
}
return cnt;
}
ll cor(ll x, ll z){
while(x != n + 1){
if(z >= s[x]){
z += s[x];
x = w[x];
}
else{
z += p[x];
x = l[x];
}
}
return z;
}
long long simulate(int x, int z){
x++;
if(z >= s[1])
return z + win[x];
if(t[x][0].first != 0){
if(t[x][19].second + z < s[1]){
z += t[x][19].second;
for(ll i = 19; i >= 0; i--)
if(t[x][i].first != 0)
x = t[x][i].first;
}
else{
for(ll i = 19; i >= 0; i--){
if(z + t[x][i].second < s[1]){
z += t[x][i].second;
x = t[x][i].first;
}
}
// one more step:
z += t[x][0].second;
x = t[x][0].first;
}
}
if(z >= s[1])
return z + win[x];
ll full = tot[comp[x]];
ll need = (s[1] - z) / full;
z += full * need;
// cout << z << ' ' << x << endl;
// cout << tot[comp[x]] << ' ' << full << ' ' << need << endl;
ll c = comp[x], pos = par_pos[x];
ll l = 0, r = (ll)(pref[c].size());
while(l < r){
ll mid = (l + r) >> 1;
ll cnt = get_sum(c, pos, mid);
if(z + cnt >= s[1])
r = mid;
else
l = mid + 1;
}
// cout << "LEN " << l << endl;
z += get_sum(c, pos, l);
// cout << pos << endl;
// for(auto i: loops[c])
// cout << i << ' ';
// cout << endl;
//
// cout << z << endl;
if(!pref[c].empty()){
pos = (pos + l) % (ll)(pref[c].size());
x = loops[comp[x]][pos];
}
return z + win[x];
}
/*
3 1
5 5 5
2 1 3
2 2 3
1 0 1
2 17
2 3
*/
/*
4 10
16 16 16 16
7 1 3 2
1 3 4 4
1 0 0 2
0 4
0 1
0 5
3 4
2 6
2 1
3 0
3 1
1 1
1 4
4 1
16 16 16 16
7 1 3 2
1 3 4 4
1 0 0 2
0 1
*/
# | 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... |