Submission #761537

#	Time	Username	Problem	Language	Result	Execution time	Memory
761537		caganyanmaz	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7038 ms	109116 KiB

dungeons

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

constexpr static int SIZE = 400001;
constexpr static int LOG_SIZE = 30;
constexpr static int DIFF = 6; // Smaller than all, bigger than 1 2 3 4 5
int64_t gain[SIZE][DIFF][LOG_SIZE];
int nxt[SIZE][DIFF][LOG_SIZE];
vector<int> ds, s, p, w, l;
int m, n;

int gi(int val)
{
        return upper_bound(ds.begin(), ds.end(), val) - ds.begin();
}

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll)
{
        n = nn;
        s = ss, p = pp, w = ww, l = ll;
        set<int> dss;
        for (int i : s)
                dss.insert(i);
        assert(dss.size() < DIFF);
        for (int i : dss)
                ds.pb(i);
        m = ds.size();
        p.pb(0), s.pb(0), w.pb(n), l.pb(n);
        for (int i = 0; i <= n; i++)
        {
                for (int j = 0; j <= m; j++)
                {
                        if (gi(s[i]) > j)
                        {
                                gain[i][j][0] = p[i];
                                nxt[i][j][0] = l[i];
                        }
                        else
                        {
                                gain[i][j][0] = s[i];
                                nxt[i][j][0] = w[i];
                        }
                }
        }
        for (int i = 1; i < LOG_SIZE; i++)
        {
                for (int j = 0; j <= n; j++)
                {
                        for (int k = 0; k <= m; k++)
                        {
                                nxt[j][k][i] = nxt[nxt[j][k][i-1]][k][i-1];
                                gain[j][k][i] = gain[j][k][i-1] + gain[nxt[j][k][i-1]][k][i-1];
                        }
                }
        }
}

int64_t simulate(int x, int zz)
{
        int64_t z = zz;
        while (x != n)
        {
                int ci = gi(z);
                for (int _next = LOG_SIZE-1; _next >= 0; _next--)
                {
                        if ((gain[x][ci][_next] + z) < ds[ci+1])
                        {
                                z += gain[x][ci][_next];
                                x = nxt[x][ci][_next];
                        }
                }
                if (z >= s[x])
                {
                        z += s[x];
                        x = w[x];
                }
                else
                {
                        z += p[x];
                        x = l[x];
                }
        }
        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

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