Submission #1276111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276111		MMihalev	던전 (IOI21_dungeons)	C++20	0 / 100	5 ms	832 KiB

dungeons

#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
const int MAX_N=4e5+5;
const int LOG=19;
const long long INF=(1LL<<62);
vector<int>wg[MAX_N];
vector<int>lg[MAX_N];
int s[MAX_N];
int p[MAX_N];
int w[MAX_N];
int l[MAX_N];
int n;

int wparent[MAX_N][LOG];
int wdep[MAX_N];
long long wdepth[MAX_N];
long long wmin[MAX_N][LOG];

void wdfs(int u)
{
    for(int j=1;j<LOG;j++)
    {
        wparent[u][j]=wparent[wparent[u][j-1]][j-1];
        wmin[u][j]=min(wmin[u][j-1],wmin[wparent[u][j-1]][j-1]);
    }

    for(int v:wg[u])
    {
        wdep[v]=wdep[u]+1;
        wdepth[v]=wdepth[u]+s[v];
        wparent[v][0]=u;
        wmin[v][0]=s[v]+wdepth[v];
        wdfs(v);
    }
}
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=1;i<=n;i++)
    {
        S[i-1]++;P[i-1]++;W[i-1]++;L[i-1]++;
        s[i]=S[i-1];
        p[i]=P[i-1];
        w[i]=W[i-1];
        l[i]=L[i-1];
        wg[w[i]].push_back(i);
        lg[l[i]].push_back(i);
    }

    wdfs(n+1);
}
void firstlose(int&x,long long&cur)
{
    for(int j=LOG-1;j>=0;j--)
    {
        if(wdep[x]-(1<<j)<0)continue;
        if(wmin[x][j]>=cur+wdepth[x])
        {
            cur+=wdepth[x];
            x=wparent[x][j];
            cur-=wdepth[x];
        }
    }
    if(x!=n+1)
    {
        if(cur>=s[x])
        {
            cur+=s[x];
            x=w[x];
        }
        else while(1);
    }
}
long long simulate(int x, int z)
{
    long long cur=z;
    x++;

    while(x!=n+1)
    {
        if(cur<s[x])
        {
            cur+=p[x];
            x=l[x];
        }
        else
        {
            firstlose(x,cur);
        }
    }

    return cur;
}

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