제출 #1195810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195810		Ludissey	던전 (IOI21_dungeons)	C++20	0 / 100	1 ms	840 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

int N; 
vector<int> s,p,w;
vector<vector<int>> nxt,l;
vector<int> tw;

const int LOG=22;

int pth(int x){
	if(x==N) return 0;
	if(tw[x]>=0) return tw[x];
	tw[x]=pth(w[x])+s[x];
	return tw[x];
}

void init(signed n, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
	N=n;
	s.resize(N);
	tw.resize(N,-1);
	p.resize(N);
	w.resize(N);
	l.resize(N+1,vector<int>(LOG,0));
	nxt.resize(N+1,vector<int>(LOG,0));
	l[N][0]=0;
	for (int i = 0; i < n; i++)
	{
		s[i]=S[i];
		p[i]=P[i];
		w[i]=W[i];
		l[i][0]=L[i];
		if(l[i][0]==N) nxt[i][0]=-1;
		else nxt[i][0]=p[i];
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 1; j < LOG; j++)
		{
			l[N][i]=N;
			l[i][j]=l[l[i][j-1]][j-1];
			if(l[i][j-1]==N) nxt[i][j]=-1;
			else if(l[l[i][j-1]][j-1]==N) nxt[i][j]=-1;
			else nxt[i][j]=nxt[i][j-1]+nxt[l[i][j-1]][j-1];
		}
	}
	for (int i = 0; i < N; i++) pth(i);
	return;
}

long long simulate(signed x, signed z) {
	int cs=z;
	int u=x;
	if(cs>=s[0]) return cs+pth(x);
	for (int j = LOG-1; j >= 0; j--)
	{
		if(nxt[u][j]==-1||nxt[u][j]+cs>=s[0]) continue;
		cs+=nxt[u][j];
		u=l[u][j];
	}
	if(l[u][0]==N){
		cs+=p[u];
		return cs;
	}else{
		cs+=nxt[u][0];
		u=l[u][0];
	}
	return cs+pth(u);
}

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