Submission #485885

#	Time	Username	Problem	Language	Result	Execution time	Memory
485885		rumen_m	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3647 ms	279092 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 400005;
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[w[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++)
      |          ~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11