Submission #1057825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057825		shjeong	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4051 ms	1683252 KiB

dungeons

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pi;
#define all(x) x.begin(),x.end()
#define rll(x) x.rbegin(),x.rend()
int table[400001][351], mx[400001][351];  //[*][*][i]: 2^(i+1)보다 작은 경우를 나타내는 sparse table, mx는 이름만 max고 min
int sum[400001][351];
vector<int> s,p,w,l;
ll n;
ll ed[400001];
int idx[26][26];
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    int cnt = 0;
    for(int i = 0 ; i < 26 ; i++){
        for(int j = 0 ; j <= i ; j++)idx[j][i] = cnt++;
    }
    s=S,p=P,w=W,l=L;
    n=N;
    for(int i = n-1 ; i >= 0 ; i--)ed[i] = ed[w[i]]+s[i];
    memset(table,-1,sizeof(table));
    fill(&mx[0][0], &mx[400000][329], 1e9);
    for(int i = 0 ; i < 26 ; i++){
        for(int j = 0 ; j < n ; j++){
            table[j][idx[0][i]] = (s[j] <= (1LL<<i) ? w[j] : l[j]);
            sum[j][idx[0][i]] = (s[j] <= (1LL<<i) ? s[j] : p[j]);
            if((1LL<<i) <= s[j] and s[j] < (1LL<<i+1)){
                mx[j][idx[0][i]] = s[j];
            }
        }
    }
    for(int k = 0 ; k < 26 ; k++){
        for(int j = 1 ; j <= k ; j++){
            for(int i = 0 ; i < n ; i++){
                if(table[i][idx[j-1][k]]<0)table[i][idx[j][k]] = -1;
                else if(table[table[i][idx[j-1][k]]][idx[j-1][k]]<0)table[i][idx[j][k]] = -1;
                else{
                    table[i][idx[j][k]] = table[table[i][idx[j-1][k]]][idx[j-1][k]];
                    mx[i][idx[j][k]] = min(mx[i][idx[j-1][k]],mx[table[i][idx[j-1][k]]][idx[j-1][k]]-sum[i][idx[j-1][k]]);
                    if(mx[i][idx[j][k]]<0)mx[i][idx[j][k]]=0;
                    sum[i][idx[j][k]] = sum[i][idx[j-1][k]] + sum[table[i][idx[j-1][k]]][idx[j-1][k]];
                    if(sum[i][idx[j][k]] > 1e9)sum[i][idx[j][k]] = 1e9;
                }
            }
        }
    }
    return;
}

long long simulate(int x, int z) {
    ll pw = z;
    for(int i = 0 ; i < 24 ; i++){
        for(int j = i ; j >= 0 ; j--){
            if(table[x][idx[j][i]]>=0 and pw+sum[x][idx[j][i]] < (1LL<<i+1) and pw < mx[x][idx[j][i]])pw += sum[x][idx[j][i]], x = table[x][idx[j][i]];
        }
        if(x==n)break;
        if(pw < s[x])pw += p[x], x = l[x];
        else pw += s[x], x = w[x];
    }
    return pw + ed[x];
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:27:51: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   27 |             if((1LL<<i) <= s[j] and s[j] < (1LL<<i+1)){
      |                                                  ~^~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:54:73: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   54 |             if(table[x][idx[j][i]]>=0 and pw+sum[x][idx[j][i]] < (1LL<<i+1) and pw < mx[x][idx[j][i]])pw += sum[x][idx[j][i]], x = table[x][idx[j][i]];
      |                                                                        ~^~

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