Submission #712650

#	Time	Username	Problem	Language	Result	Execution time	Memory
712650		danikoynov	던전 (IOI21_dungeons)	C++17	50 / 100	7094 ms	527068 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 4e5 + 10, maxlog = 25;

int n, w[maxn], l[maxn];
ll s[maxn], p[maxn];

vector < int > child[maxn];

struct jump
{
    ll sum, max_strenght;
    int ver;


};

jump dp[maxlog][maxn], fp[maxlog][maxn];
void dfs(int v)
{
    dp[0][v].ver = w[v];
    dp[0][v].sum = s[v];
    dp[0][v].max_strenght = s[v];
    for (int j = 1; j < maxlog; j ++)
    {
        dp[j][v].sum = dp[j - 1][v].sum + dp[j - 1][dp[j - 1][v].ver].sum;
        dp[j][v].ver = dp[j - 1][dp[j - 1][v].ver].ver;
        dp[j][v].max_strenght = max(dp[j - 1][v].max_strenght, dp[j - 1][dp[j - 1][v].ver].max_strenght);
    }

    for (int u : child[v])
    {
        dfs(u);
    }
}

bool all_same = true;
set < ll > st;
vector < ll > values;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    n = N;
    for (int i = 0; i < n; i ++)
    {
        s[i] = S[i];
        p[i] = P[i];
        w[i] = W[i];
        l[i] = L[i];
        st.insert(s[i]);

        child[w[i]].push_back(i);
    }
    for (auto it : st)
        values.push_back(it);

    for (int i = 1; i < n; i ++)
    {
        if (s[i] != s[i - 1])
            all_same = false;
    }

    for (int j = 0; j < maxlog; j ++)
        dp[j][n].ver = n;
    w[n] = n;
    l[n] = n;
    dfs(n);

    for (int i = 0; i <= n; i ++)
    {
        fp[0][i].ver = l[i];
        fp[0][i].sum = p[i];
        fp[0][i].max_strenght = s[i];
    }

    for (int j = 1; j < maxlog; j ++)
    {
        for (int i = 0; i <= n; i ++)
        {
            fp[j][i].ver = fp[j - 1][fp[j - 1][i].ver].ver;
            fp[j][i].sum = fp[j - 1][fp[j - 1][i].ver].sum + fp[j - 1][i].sum;
            fp[j][i].max_strenght = min(fp[j - 1][fp[j - 1][i].ver].max_strenght, fp[j - 1][i].max_strenght);
        }
    }
    return;
}

long long simulate(int x, int z)
{
    ll strength = z;
    while(x != n)
    {
        ///cout << x << " : " << strength << endl;
        if (strength >= s[x])
        {
            for (int bit = maxlog - 1; bit >= 0; bit --)
            {
                if (dp[bit][x].max_strenght <= strength)
                {
                    strength += dp[bit][x].sum;
                    x = dp[bit][x].ver;
                }
            }
            ///cout << x << endl;
        }
        else
        {
            //strength += p[x];
            //x = l[x];
            //continue;
            ///cout << "start " << strength << endl;
            ll bef = strength;
            int tp  =0;
            for (int i = 0; i < (int)(values.size()); i ++)
            {
                if (strength >= values[i])
                    continue;
                int new_x = x;
                ll cur_strength = strength, min_strength = 1e15;
                for (int bit = maxlog - 1; bit >= 0; bit --)
                {
                    if (fp[bit][new_x].ver == n)
                        continue;
                    if (cur_strength + fp[bit][new_x].sum < values[i])
                    {
                        ///cout << new_x << " jump " << bit << " " << fp[bit][new_x].sum << endl;
                        min_strength = min(min_strength, fp[bit][new_x].max_strenght);
                        cur_strength += fp[bit][new_x].sum;
                        new_x = fp[bit][new_x].ver;
                    }
                }
                min_strength = min(min_strength, fp[0][new_x].max_strenght);
                 ///cout << new_x << " jump " << 0 << " " << fp[0][new_x].max_strenght << endl;
                cur_strength += fp[0][new_x].sum;
                new_x = fp[0][new_x].ver;

                ///cout << min_strength << " ----------- " << strength << endl;
                if (min_strength <= strength)
                {

                    ll to_add = 0;
                    for (int bit = maxlog - 1; bit >= 0; bit --)
                    {
                        if (fp[bit][new_x].ver == n)
                            continue;
                        if (fp[bit][x].max_strenght > strength)
                        {
                            to_add += fp[bit][x].sum;
                            x = fp[bit][x].ver;
                        }
                    }
                    strength += to_add;
                }
                else
                {
                    tp = 1;
                    ///cout << "skip " << " " << new_x << " " << values[i] << " " << cur_strength << " " << min_strength << endl;
                    strength = cur_strength;
                    x = new_x;
                }
            }
            if (tp == 1 && strength == bef)
            {
                cout << 1 / 0 << endl;
                exit(0);
            }


        }
    }
    return strength;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:168:27: warning: division by zero [-Wdiv-by-zero]
  168 |                 cout << 1 / 0 << endl;
      |                         ~~^~~

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