Submission #485837

#	Time	Username	Problem	Language	Result	Execution time	Memory
485837		rumen_m	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	139 ms	34756 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 400005;
const long long logn = 35;
long long nextt[maxn][logn],add[maxn][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(i=0;i<n;i++)
    {
        nextt[i][0] = l[i];
        add[i][0] = p[i];
    }
    nextt[n][0]  = n;
    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];
        }
    }
    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;
	long long S = s[0];
	long long i;
	for(i = logn-1;i>=0;i--)
    {
        if(z+add[x][i] < S)
        {
            z+=add[x][i];
            x = nextt[x][i];
        }
    }
    if(z<S){
    z+=add[x][0];
    x = nextt[x][0];}
    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:25:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(i=0;i<_s.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:28:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(i=0;i<_p.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:31:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(i=0;i<_w.size();i++)
      |          ~^~~~~~~~~~
dungeons.cpp:34:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(i=0;i<_l.size();i++)
      |          ~^~~~~~~~~~

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