#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int const N=4e5+10;
long long wi[N],lo[N],po[N],st[N];
int nn;
set<int>sr;
vector<int>nei[N]={};
long long head[N]={},cost[N]={},cost1[N]={};
int vis[N]={};
vector<vector<pair<int,long long>>>heads;
void dfs(int n,int val=0)
{
cost1[n]=val*st[0];
for (auto i:nei[n])
{
dfs(i,val+1);
}
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
nn=n;
for (int i=0;i<n;i++)
{
wi[i]=w[i];
lo[i]=l[i];
st[i]=s[i];
po[i]=p[i];
nei[w[i]].push_back(i);
head[i]=-1;
sr.insert(s[i]);
}
dfs(n);
int o=0;
for (int i=0;i<n;i++)
{
if (head[i]==-1)
{
int j=i;
vector<int>temp;
while (!vis[j])
{
temp.push_back(j);
vis[j]=1;
j=lo[j];
}
o+=(j==i);
if (head[j]==-1)
{
int k;
for (k=0;k<temp.size();k++)
if (temp[k]==j)
break;
long long z=0;
for (int l=k-1;l>=0;l--)
{
z+=po[temp[l]];
cost[temp[l]]=z;
}
z=0;
for (int l=temp.size();l>k;l--)
{
z+=po[temp[l]];
cost[temp[l]]=z;
}
cost[temp[k]]=0;
for (auto t:temp)
head[t]=heads.size();
reverse(begin(temp),end(temp));
while (temp.back()!=j)
{
temp.pop_back();
}
vector<pair<int,long long>>pre(temp.size()+1);
reverse(begin(temp),end(temp));
pre[0]={temp[0],0};
for (int l=1;l<temp.size();l++)
pre[l]={temp[l],pre[l-1].second+po[temp[l-1]]};
pre[temp.size()]={temp[0],pre[temp.size()-1].second+po[temp.back()]};
heads.push_back(pre);
}
else
{
for (auto k:temp)
{
head[k]=head[j];
}
long long z=cost[j];
reverse(begin(temp),end(temp));
for (auto k:temp)
{
z+=lo[k];
cost[k]=z;
}
}
}
}
}
bool yu=0;
long long simulate(int i, int z)
{
if (sr.size()==1)
{
long long f=*begin(sr);
long long ans=z;
if (ans+cost[i]>f)
{
while (ans<f)
{
ans+=po[i];
i=lo[i];
}
ans+=cost1[i];
}
else
{
ans+=cost[i];
long long y=heads[head[i]].back().second;
long long r=(f-ans)/y;
r=max(r,0LL);
ans+=y*r;
int st=-1,en=heads[head[i]].size();
r=f-ans;
while (st+1<en)
{
int mid=(st+en)/2;
if (heads[head[i]][mid].second>=r)
en=mid;
else
st=mid;
}
if (yu==0)
{
ans+=heads[head[i]][en].second;
ans+=cost1[heads[head[i]][en].first];
}
yu=1;
}
return ans;
}
long long ans=z;
while (i!=nn)
{
if (ans>=st[i])
{
ans+=st[i];
i=wi[i];
}
else
{
ans+=po[i];
i=lo[i];
}
}
return ans;
}
Compilation message
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (k=0;k<temp.size();k++)
| ~^~~~~~~~~~~~
dungeons.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int l=1;l<temp.size();l++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
24920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 2 |
Execution timed out |
7091 ms |
66504 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
31312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
31312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
31312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 2 |
Execution timed out |
7091 ms |
66504 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
