| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1334920 | activedeltorre | 던전 (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include "dungeons.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
int hp[400005];
int addw[400005];
int addl[400005];
int muchw[400005];
int muchl[400005];
int spar[400005];
int nmax;
using namespace std;
vector<int>adj[400005];
int bl[20][400005];
void dfs(int curr,int par)
{
spar[curr]=spar[par]+addw[curr];
bl[0][curr]=par;
for(int i=1;i<=19;i++)
{
bl[i][curr]=bl[i-1][bl[i-1][curr]];
}
for(auto k:adj[curr])
{
dfs(k,curr);
}
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
nmax=n;
for(int i=1;i<=n;i++)
{
hp[i]=s[i-1];
addw[i]=s[i-1];
addl[i]=p[i-1];
muchw[i]=w[i-1]+1;
muchl[i]=l[i-1]+1;
}
for(int i=n-1;i>=1;i--)
{
while(hp[i]+addw[i]>=hp[muchw[i]] && muchw[i]!=n+1)
{
addw[i]=addw[i]+addw[muchw[i]];
muchw[i]=muchw[muchw[i]];
}
//cout<<i<<" "<<addw[i]<<" "<<muchw[i]<<'\n';
}
/*
for(int i=1;i<=n;i++)
{
adj[w[i]].push_back(i);
}*/
//dfs(n+1,n+1);
return;
}