Submission #485868

#	Time	Username	Problem	Language	Result	Execution time	Memory
485868		rumen_m	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	5039 ms	1097088 KiB

dungeons

#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;
long long nextt[maxn][logn][logn],add[maxn][logn][logn],treshold[maxn][logn][logn];
long long sums[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]);
    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(int t = 0; t<logn; t++)
        {
            long long from = (1<<t);
            long long to = (1<<(t+1));
            for(i=0;i<n;i++)
            {
                if(s[i]>to){
                    nextt[i][0][t] = l[i];
                    add[i][0][t] = p[i];
                    treshold[i][0][t] = INF;
                }
                else
                if(s[i]<=from)
                {
                    nextt[i][0][t] = w[i];
                    add[i][0][t] = s[i];
                    treshold[i][0][t] = INF;

                }
                else
                {
                    nextt[i][0][t] = l[i];
                    add[i][0][t] = p[i];
                    treshold[i][0][t] = s[i];

                }
            }
            nextt[n][0][t]  = n;
            treshold[n][0][t] = INF;//cout<<t<<endl;
            for(i=1;i<logn;i++)
            {
                for(j=0;j<=n;j++)
                {
                    nextt[j][i][t] = nextt[nextt[j][i-1][t]][i-1][t];
                    add[j][i][t] = add[j][i-1][t]+add[nextt[j][i-1][t]][i-1][t];
                    treshold[j][i][t] = max((long long)0,min(treshold[j][i-1][t],treshold[nextt[j][i-1][t]][i-1][t]-add[j][i-1][t]));
                 //   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;
	if(x==n)return z;// cout<<"&&"<<n<<endl;
	int i;
	for(int t = 0; t < logn; t++)
    {
       // cout<<x<<" "<<z<<endl;

        long long to = (1<<(t+1));
            for(i = logn-1; i>=0;i--)
            {
              //  cout<<i<<" curr: "<<x<<" "<<z<<endl;
                if(x==n)return z;
                if(treshold[x][i][t]>z&&add[x][i][t]+z < to)
                {
                    z += add[x][i][t];
                    x = nextt[x][i][t];
                }
            }
           // cout<<"predi last: "<<x<<" "<<z<<endl;
            if(x==n)return z;
            if(z<to)
            {
               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:26:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(i=0;i<_s.size();i++)
      |          ~^~~~~~~~~~
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<_p.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<_w.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<_l.size();i++)
      |          ~^~~~~~~~~~

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