Submission #610997

#	Time	Username	Problem	Language	Result	Execution time	Memory
610997		Ozy	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	165 ms	40688 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)

#define MAX 400000
#define anc first
#define sum second

lli N,fuerza;
pair<lli,lli> st[MAX+2][32];
vector<lli> hijos[MAX+2];
lli camino[MAX+2];

void dfs(lli pos, lli padre, lli prof) {
    camino[pos] = prof*fuerza;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;
        dfs(h,pos,prof+1);
    }
}

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {

	N = n;
	fuerza = s[0];
	rep(i, 0, n-1) st[i][0] = {l[i],p[i]};
	rep(i, 0, 30) st[n][i] = {n,0};

	lli a;
	rep(j,1,30) {
        rep(i,0,n-1) {
            a = st[i][j-1].anc;
            st[i][j].anc = st[a][j-1].anc;
            st[i][j].sum = st[i][j-1].sum + st[a][j-1].sum;
        }
	}

	//camino ganador
	rep(i,0,n-1) {
        a = w[i];
        hijos[a].push_back(i);
	}

	dfs(n,-1,0);
}

long long simulate(int x, int k) {

    lli z = k;
    if (z < fuerza) {
        repa(i,25,0) {
            if ((z + st[x][i].sum) < fuerza) {
                z += st[x][i].sum;
                x = st[x][i].anc;
            }
        }

        z += st[x][0].sum;
        x = st[x][0].anc;
    }
	z += camino[x];
	return z;
}

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