Submission #761768

#	Time	Username	Problem	Language	Result	Execution time	Memory
761768		caganyanmaz	던전 (IOI21_dungeons)	C++17	50 / 100	7043 ms	639988 KiB

dungeons

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

constexpr static int SIZE = 400001;
constexpr static int LOG_SIZE = 40;
int win_next[SIZE][LOG_SIZE];
int64_t win_gain[SIZE][LOG_SIZE];
int64_t win_max[SIZE][LOG_SIZE];
int lose_next[SIZE][LOG_SIZE];
int64_t lose_gain[SIZE][LOG_SIZE];
int64_t lose_min[SIZE][LOG_SIZE];

int n;
void init(int nn, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
        n = nn;
        l.pb(n);
        w.pb(n);
        s.pb(0);
        p.pb(0);
        for (int i = 0; i <= n; i++)
        {
                win_next[i][0] = w[i];
                win_max[i][0] = s[i];
                win_gain[i][0] = s[i];
                lose_next[i][0] = l[i];
                lose_min[i][0] = s[i];
                lose_gain[i][0] = p[i];
        }
        for (int i = 1; i < LOG_SIZE; i++)
        {
                for (int j = 0; j <= n; j++)
                {
                        win_next[j][i] = win_next[win_next[j][i-1]][i-1];
                        win_gain[j][i] = win_gain[j][i-1] + win_gain[win_next[j][i-1]][i-1];
                        win_max[j][i] = max(win_max[j][i-1], win_max[win_next[j][i-1]][i-1] - win_gain[j][i-1]);
                        lose_next[j][i] = lose_next[lose_next[j][i-1]][i-1];
                        lose_gain[j][i] = lose_gain[j][i-1] + lose_gain[lose_next[j][i-1]][i-1];
                        lose_min[j][i] = min(lose_min[j][i-1], lose_min[lose_next[j][i-1]][i-1] - lose_gain[j][i-1]);
                }
        }
}

int64_t simulate(int x, int zz)
{
        int64_t z = zz;
        while (x != n)
        {
                int _next = LOG_SIZE-1;
                for (int _next = LOG_SIZE-1; _next >= 0; _next--)
                {
                        if (win_max[x][_next] <= z)
                        {
                                z += win_gain[x][_next];
                                x = win_next[x][_next];
                        }
                }
                for (int _next = LOG_SIZE-1; _next >= 0; _next--)
                {
                        if (lose_min[x][_next] > z)
                        {
                                z += lose_gain[x][_next];
                                x = lose_next[x][_next];
                        }
                }
        }
        return z;
}



#ifdef __DEBUG__
int main()
{
        int n;
        cin >> n;
        vector<int> ss(n), pp(n), ww(n), ll(n);
        for (int i = 0; i < n; i++)
                cin >> ss[i] >> pp[i] >> ww[i] >> ll[i];
        init(n, ss, pp, ww, ll);
        int q;
        cin >> q;
        while (q--)
        {
                int x, z;
                cin >> x >> z;
                cout << simulate(x, z) <<"\n";
        }
}
#endif

Compilation message (stderr)

dungeons.cpp: In function 'int64_t simulate(int, int)':
dungeons.cpp:50:21: warning: unused variable '_next' [-Wunused-variable]
   50 |                 int _next = LOG_SIZE-1;
      |                     ^~~~~

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