Submission #805325

#	Time	Username	Problem	Language	Result	Execution time	Memory
805325		SamAnd	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6305 ms	908536 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 400005;
const int m = 28;
const ll INF = 1000000009000000009;

int n;
vector<int> S, P, W, L;

vector<int> t[N];

ll st[m][N];
int ut[m][N];
void dfst(int x, int j)
{
    if (x == n || S[x] >= (1 << j))
    {
        st[j][x] = 0;
        ut[j][x] = x;
    }
    for (int i = 0; i < sz(t[x]); ++i)
    {
        int h = t[x][i];
        ut[j][h] = ut[j][x];
        st[j][h] = st[j][x] + S[h];
        dfst(h, j);
    }
}

pair<int, ll> u[m][N];

//////////////////////////////////////////////////////////////

vector<vector<int> > vv;
int c[N];
bool dfsc(int x, int j)
{
    c[x] = 1;
    int h = u[j][x].fi;
    if (!c[h])
    {
        if (dfsc(h, j))
        {
            c[x] = 2;
            return true;
        }
    }
    else if (c[h] == 1)
    {
        vector<int> v;
        while (h != x)
        {
            v.push_back(h);
            h = u[j][h].fi;
        }
        v.push_back(x);
        vv.push_back(v);
        c[x] = 2;
        return true;
    }
    c[x] = 2;
    return false;
}

int minc[m][N];
ll sc[m][N];

vector<pair<int, ll> > g[N];
int q[N];
ll d[m][N];
void dfs0(int x, int j)
{
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        d[j][h] = d[j][x] + g[x][i].se;
        dfs0(h, j);
        q[x] += q[h];
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (q[h] > q[g[x][0].fi])
        {
            swap(g[x][i], g[x][0]);
        }
    }
}

int tin[m][N], tout[m][N], ti[m], rtin[m][N];
int f[m][N];
int p0[m][N];
ll minf[m][N];
void dfs1(int x, int j)
{
    tin[j][x] = ++ti[j];
    rtin[j][tin[j][x]] = x;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        p0[j][h] = x;
        if (i == 0)
        {
            f[j][h] = f[j][x];
            minf[j][h] = minf[j][x];
            minf[j][h] = min(minf[j][h], d[j][h] + S[h]);
        }
        else
        {
            f[j][h] = h;
            minf[j][h] = d[j][h] + S[h];
        }
        dfs1(h, j);
    }
    tout[j][x] = ti[j];
}

ll minu[m][N * 4];

ll bu[N];
void bil(int j, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        minu[j][pos] = bu[tl];
        return;
    }
    int m = (tl + tr) / 2;
    bil(j, tl, m, pos * 2);
    bil(j, m + 1, tr, pos * 2 + 1);
    minu[j][pos] = min(minu[j][pos * 2], minu[j][pos * 2 + 1]);
}

void ubd(int j, int tl, int tr, int x, ll y, int pos)
{
    if (tl == tr)
    {
        minu[j][pos] = y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(j, tl, m, x, y, pos * 2);
    else
        ubd(j, m + 1, tr, x, y, pos * 2 + 1);
    minu[j][pos] = min(minu[j][pos * 2], minu[j][pos * 2 + 1]);
}

int qry(int j, int tl, int tr, int l, int r, ll y, int pos)
{
    if (l > r)
        return ti[j] + 1;
    if (tl == l && tr == r)
    {
        if (minu[j][pos] > y)
            return ti[j] + 1;
        if (tl == tr)
            return tl;
    }
    int m = (tl + tr) / 2;
    int ans = qry(j, m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
    if (ans <= ti[j])
        return ans;
    return qry(j, tl, m, l, min(m, r), y, pos * 2);
}

int qry(int j, int x, ll y)
{
    int qq = 0;
    while (1)
    {
        ++qq;
        assert(qq <= 20);
        if (minf[j][x] <= y)
        {
            int ans = qry(j, 1, ti[j], tin[j][f[j][x]], tin[j][x], y, 1);
            assert(ans <= ti[j]);
            return rtin[j][ans];
        }
        x = f[j][x];
        if (d[j][x] == 0)
            return x;
        x = p0[j][x];
    }
}

void init(int NN, std::vector<int> SS, std::vector<int> PP, std::vector<int> WW, std::vector<int> LL) {
    n = NN;
    S = SS;
    P = PP;
    W = WW;
    L = LL;

    for (int i = 0; i < n; ++i)
    {
        t[W[i]].push_back(i);
    }

    for (int j = 0; j < m; ++j)
    {
        vv.clear();
        for (int i = 0; i <= n; ++i)
        {
            g[i].clear();
            c[i] = 0;
        }

        dfst(n, j);

        for (int x = 0; x < n; ++x)
        {
            if (S[x] >= (1 << j))
            {
                u[j][x] = m_p(ut[j][L[x]], P[x] + st[j][L[x]]);
            }
        }
        u[j][n] = m_p(n, 0);

////////////////////////////////////////////////////////////////////////////

        for (int x = 0; x <= n; ++x)
        {
            if (x == n || S[x] >= (1 << j))
            {
                if (!c[x])
                {
                    dfsc(x, j);
                }
            }
        }
        for (int x = 0; x <= n; ++x)
        {
            c[x] = 0;
        }
        for (int i = 0; i < sz(vv); ++i)
        {
            c[vv[i][0]] = 1;
            if (vv[i][0] == n)
            {
                assert(sz(vv[i]) == 1);
                continue;
            }
            minc[j][vv[i][0]] = S[vv[i][0]];
            for (int k = 0; k < sz(vv[i]); ++k)
            {
                minc[j][vv[i][0]] = min(minc[j][vv[i][0]], S[vv[i][k]]);
                sc[j][vv[i][0]] += u[j][vv[i][k]].se;
            }
        }
        for (int x = 0; x <= n; ++x)
        {
            if (x == n || S[x] >= (1 << j))
            {
                if (!c[x])
                    g[u[j][x].fi].push_back(m_p(x, u[j][x].se));
            }
        }
        for (int x = 0; x <= n; ++x)
        {
            if (c[x])
            {
                dfs0(x, j);
                f[j][x] = x;
                if (x < n)
                    minf[j][x] = S[x];
                dfs1(x, j);
            }
        }
        for (int x = 0; x <= n; ++x)
        {
            if (x == n || S[x] >= (1 << j))
            {
                if (x != n)
                    bu[tin[j][x]] = d[j][x] + S[x];
                    //ubd(j, 1, ti[j], tin[j][x], d[j][x] + S[x], 1);
                else
                {
                    assert(d[j][x] == 0);
                    bu[tin[j][x]] = d[j][x];
                    //ubd(j, 1, ti[j], tin[j][x], d[j][x], 1);
                }
            }
        }
        bil(j, 1, ti[j], 1);
    }
}

long long simulate(int x, int Z) {
    ll z = Z;
    int qq = 0;
    while (x != n)
    {
        for (int j = m - 1; j >= 0; --j)
        {
            if (z >= (1 << j))
            {
                z += st[j][x];
                x = ut[j][x];
                /*while (x != n && z < S[x])
                {
                    z += u[j][x].se;
                    x = u[j][x].fi;
                }*/
                while (x != n && z < S[x])
                {
                    ++qq;
                    int p = qry(j, x, z + d[j][x]);
                    z += d[j][x] - d[j][p];
                    x = p;
                    if (x != n && z < S[x])
                    {
                        ll q = (minc[j][x] - z);
                        if (q < 0)
                            q = 0;
                        else
                            q = (q / sc[j][x]);
                        z += q * sc[j][x];
                        if (z < S[x])
                        {
                            z += u[j][x].se;
                            x = u[j][x].fi;
                        }
                    }
                }
                if (x != n)
                {
                    assert(z >= S[x]);
                    z += S[x];
                    x = W[x];
                }
                break;
            }
        }
    }
    assert(qq <= m * 3);
	return z;
}

/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3

*/

Compilation message (stderr)

dungeons.cpp: In function 'void dfs0(int, int)':
dungeons.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
dungeons.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
dungeons.cpp: In function 'void dfs1(int, int)':
dungeons.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < g[x].size(); ++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