Submission #440829

#	Time	Username	Problem	Language	Result	Execution time	Memory
440829		denkendoemeer	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4570 ms	868420 KiB

dungeons

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
vector<int>s,p,w,l,g[400005],we[400005];
ll sum[4][25][400005],mini[4][25][400005],add[400005],step[10];
int pre[4][25][400005],n;
void dfs(int nod,ll val)
{
    add[nod]=val;
    for(int i=0;i<g[nod].size();i++)
        dfs(g[nod][i],val+we[nod][i]);
}
void init(int n2,vector<int>s2,vector<int>p2,vector<int>w2,vector<int>l2)
{
    n=n2;
    s=s2;
    p=p2;
    w=w2;
    l=l2;
    w.push_back(n);
    l.push_back(n);
    s.push_back(0);
    p.push_back(0);
    step[0]=1;
    for(int i=1;i<10;i++)
        step[i]=step[i-1]*57;
    for(int k=0;k<4;k++){
        int st=step[k];
        for(int i=0;i<n;i++){
            if (s[i]<=st){
                pre[k][0][i]=w[i];
                sum[k][0][i]=s[i];
                mini[k][0][i]=inf;
            }
            else{
                pre[k][0][i]=l[i];
                sum[k][0][i]=p[i];
                mini[k][0][i]=s[i];
            }
        }
        pre[k][0][n]=n;
        sum[k][0][n]=0;
        mini[k][0][n]=inf;
        for(int j=1;j<25;j++){
            for(int i=0;i<=n;i++){
                pre[k][j][i]=pre[k][j-1][pre[k][j-1][i]];
                sum[k][j][i]=sum[k][j-1][i]+sum[k][j-1][pre[k][j-1][i]];
                if (sum[k][j][i]>inf)
                    sum[k][j][i]=inf;
                mini[k][j][i]=min(mini[k][j-1][i],mini[k][j-1][pre[k][j-1][i]]-sum[k][j-1][i]);
            }
        }
    }
    for(int i=0;i<n;i++){
        g[w[i]].push_back(i);
        we[w[i]].push_back(s[i]);
    }
    dfs(n,0);
}
ll simulate(int x,int z)
{
    ll st=z;
    for(int k=0;k<4;k++){
        while(1){
            if (st>=step[k+1] || x==n)
                break;
            for(int j=24;j>=0;j--)
                if (mini[k][j][x]>st){
                    st+=sum[k][j][x];
                    x=pre[k][j][x];
                }
            st+=s[x];
            x=w[x];
        }
    }
    return st+add[x];
}

Compilation message (stderr)

dungeons.cpp: In function 'void dfs(int, long long int)':
dungeons.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<g[nod].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