제출 #712624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712624		danikoynov	던전 (IOI21_dungeons)	C++17	0 / 100	7030 ms	39960 KiB

dungeons

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

using namespace std;
typedef long long ll;

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

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];
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);
    }
}

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];

        child[w[i]].push_back(i);
    }
    for (int j = 0; j < maxlog; j ++)
        dp[j][n].ver = n;
    w[n] = n;
    dfs(n);
    return;
}

long long simulate(int x, int z)
{
    ll strength = z;
    while(x != n)
    {
        if (strength >= s[x])
        {
            for (int bit = maxlog - 1; bit >= 0; bit --)
            {
                if (dp[bit][x].max_strenght < strength + s[x])
                {
                    strength += dp[bit][x].sum;
                    x = dp[bit][x].ver;
                }
            }
            ///cout << x << endl;
        }
        else
        {
            strength += p[x];
            x = l[x];
        }
    }
    return strength;
}

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