제출 #1330592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1330592		BigBadBully	던전 (IOI21_dungeons)	C++20	100 / 100	6683 ms	1806316 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int inf = 2e18;
const int bv = 25;
const int mb = 9;

signed nxt[25][9][400001];
int mini[25][9][400001];
int sum[25][9][400001];
vector<int> stg,win,lose,pen;
void init(signed _n, vector<signed> _s, vector<signed> _p, vector<signed> _w, vector<signed> _l) {
	int n = _n;
    vector<int> s(n),p(n),w(n),l(n);
    for(int i = 0; i< n; i++)s[i]=_s[i],p[i]=_p[i],w[i]=_w[i],l[i]=_l[i];
    stg = s;
    win = w,lose = l,pen = p;
    vector<int> par(n+1,n);
    for(int i = 0; i < n; i++)
        par[i] = l[i];
    for(int i = 0; i < 9;i++)
        for(int j =0;j<25;j++)
            for(int k = 0; k <=n;k++)
                nxt[i][j][k]=n,mini[i][j][k]=inf,sum[i][j][k]=0;
    vector<int> c(n+1,0);
    for(int i = 0; i < n; i++)c[i]=p[i];
    for(int b = 0;b < bv;b++)
    {
        for(int i = 0; i < n; i++)
        {
            nxt[b][0][i] = par[i],sum[b][0][i] = c[i];
            if(__lg(s[i])==b)
                mini[b][0][i] = s[i];
            else
                mini[b][0][i] = inf;
        }
        for(int bit=1;bit<mb;bit++)
            for(int i = 0; i < n; i++)
            {
                nxt[b][bit][i] = nxt[b][bit-1][i];
                sum[b][bit][i] = sum[b][bit-1][i];
                mini[b][bit][i] = mini[b][bit-1][i];
                for(int it = 0;it < (1<<((bv+mb-1)/mb))-1;it++)
                {
                    mini[b][bit][i] = min(mini[b][bit][i],mini[b][bit-1][nxt[b][bit][i]]-sum[b][bit][i]);
                    sum[b][bit][i]+=sum[b][bit-1][nxt[b][bit][i]];
                    nxt[b][bit][i] = nxt[b][bit-1][nxt[b][bit][i]];
                }
            }
        for(int i = 0; i < n;i++)
            if(__lg(s[i])<=b)
                par[i] = w[i],c[i]=s[i];
    }
    return;
}

void adv(int&x,int&z)
{
    if(z>=stg[x])
            z+=stg[x],x = win[x];
        else
            z+=pen[x],x=lose[x];
}

long long simulate(signed _x, signed _z) {
    int x = _x,z=_z;
    int n = stg.size();
    for(int b = 0;b < bv&&x!=n;b++)
    {
        for(int bit = mb-1;bit >= 0;bit--)
            while((b==bv-1||sum[b][bit][x]+z < (1ll<<b+1)) && nxt[b][bit][x]!=n && 
                (mini[b][bit][x]>z))
                    z+=sum[b][bit][x],x = nxt[b][bit][x];
        
        adv(x,z);
    }
    return z;
}
#undef int

컴파일 시 표준 에러 (stderr) 메시지

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:28:29: warning: iteration 9 invokes undefined behavior [-Waggressive-loop-optimizations]
   28 |                 nxt[i][j][k]=n,mini[i][j][k]=inf,sum[i][j][k]=0;
      |                 ~~~~~~~~~~~~^~
dungeons.cpp:26:23: note: within this loop
   26 |         for(int j =0;j<25;j++)
      |                      ~^~~

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