제출 #804689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804689		SamAnd	던전 (IOI21_dungeons)	C++17	37 / 100	7054 ms	275728 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 400005;
const int m = 28;

int n;
vector<int> S, P, W, L;

vector<int> t[N];

ll st[m][N];
int ut[m][N];
void dfst(int x, int j)
{
    if (x == n || S[x] >= (1 << j))
    {
        st[j][x] = 0;
        ut[j][x] = x;
    }
    for (int i = 0; i < sz(t[x]); ++i)
    {
        int h = t[x][i];
        ut[j][h] = ut[j][x];
        st[j][h] = st[j][x] + S[h];
        dfst(h, j);
    }
}

pair<int, ll> u[m][N];

void init(int NN, std::vector<int> SS, std::vector<int> PP, std::vector<int> WW, std::vector<int> LL) {
    n = NN;
    S = SS;
    P = PP;
    W = WW;
    L = LL;

    for (int i = 0; i < n; ++i)
    {
        t[W[i]].push_back(i);
    }

    for (int j = 0; j < m; ++j)
    {
        dfst(n, j);

        for (int x = 0; x < n; ++x)
        {
            if (S[x] >= (1 << j))
            {
                u[j][x] = m_p(ut[j][L[x]], P[x] + st[j][L[x]]);
            }
        }
        u[j][n] = m_p(n, 0);
    }
}

long long simulate(int x, int Z) {
    ll z = Z;
    while (x != n)
    {
        for (int j = m - 1; j >= 0; --j)
        {
            if (z >= (1 << j))
            {
                z += st[j][x];
                x = ut[j][x];
                while (x != n && z < S[x])
                {
                    z += u[j][x].se;
                    x = u[j][x].fi;
                }
                if (x != n)
                {
                    assert(z >= S[x]);
                    z += S[x];
                    x = W[x];
                }
                break;
            }
        }
    }
	return z;
}

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