Submission #485880

#TimeUsernameProblemLanguageResultExecution timeMemory
485880rumen_mDungeons Game (IOI21_dungeons)C++17
13 / 100
1841 ms34772 KiB
#include "dungeons.h" #include <vector> #include <bits/stdc++.h> using namespace std; const long long maxn = 50005; const long long logn = 24; const long long INF = 1e18; const int C = 3000; int where[logn]; long long nextt[maxn][logn],add[maxn][logn],treshold[maxn][logn]; long long sums[maxn],maxs[maxn]; bool vis[maxn]; long long n; vector <long long> s,p,w,l; long long dfs(long long v) { if(v==n)return 0; if(vis[v])return sums[v]; sums[v] = s[v] + dfs(w[v]); maxs[v] =max(s[v],maxs[v]); vis[v] = 1; return sums[v]; } void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) { long long i,j; n = _n; s.resize(_s.size()); for(i=0;i<_s.size();i++) s[i] = _s[i]; p.resize(_p.size()); for(i=0;i<_p.size();i++) p[i] = _p[i]; w.resize(_w.size()); for(i=0;i<_w.size();i++) w[i] = _w[i]; l.resize(_l.size()); for(i=0;i<_l.size();i++) l[i] = _l[i]; for(i=0;i<n;i++) { if(s[i]<=C) { nextt[i][0] = w[i]; add[i][0] = s[i]; treshold[i][0]= INF; } else { nextt[i][0] = l[i]; add[i][0]= p[i]; treshold[i][0] = s[i]; } } nextt[n][0] = n; treshold[n][0] = INF;//cout<<t<<endl; for(i=1;i<logn;i++) { for(j=0;j<=n;j++) { nextt[j][i]= nextt[nextt[j][i-1]][i-1]; add[j][i] = add[j][i-1]+add[nextt[j][i-1]][i-1]; treshold[j][i] = max((long long)0,min(treshold[j][i-1],treshold[nextt[j][i-1]][i-1]-add[j][i-1])); // cout<<j<<" "<<i<<" "<<t<<" -> "<<nextt[j][i][t]<<" "<<add[j][i][t]<<" "<<treshold[j][i][t]<<endl; } } for(i=0;i<=n;i++) { dfs(i); } } long long simulate(int _x, int _z) { long long x = _x; long long z = _z; while(z <= C) { if(x==n)return z; if(z>=s[x]) { z+=s[x]; x = w[x]; } else { z+=p[x]; x = l[x]; } } if(x==n)return z;// cout<<"&&"<<n<<endl; int i; // cout<<x<<" "<<z<<endl; bool fl = true; while(fl) { fl=0; for(i = logn-1; i>=0;i--) { // cout<<i<<" curr: "<<x<<" "<<z<<endl; if(x==n)return z; if(treshold[x][i]>z) { z += add[x][i]; x = nextt[x][i]; fl = true; break; } } if(x==n)return z; if(z>=s[x]) { z+=s[x]; x = w[x]; } else { z+=p[x]; x = l[x]; } if(x==n)return z; fl = true; if(maxs[x]<=z) { z+=sums[x]; return z; } } // cout<<"predi last: "<<x<<" "<<z<<endl; if(x==n)return z; if(s[x]>z) { z+=p[x]; x = l[x]; } else { z+=s[x]; x = w[x]; } // cout<<"final: "<<x<<" "<<z<<endl; z += sums[x]; return z; }

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:29:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(i=0;i<_s.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:32:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(i=0;i<_p.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:35:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(i=0;i<_w.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:38:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(i=0;i<_l.size();i++)
      |          ~^~~~~~~~~~
#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...