oj.uz

Submission #805325

# Submission time Handle Problem Language Result Execution time Memory
805325 2023-08-03T15:17:32 Z SamAnd Dungeons Game (IOI21_dungeons) C++17
100 / 100
 6305 ms 908536 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21076 KB Output is correct
2 Correct 10 ms 21360 KB Output is correct
3 Correct 16 ms 22376 KB Output is correct
4 Correct 178 ms 92512 KB Output is correct
5 Correct 16 ms 24240 KB Output is correct
6 Correct 170 ms 92472 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23856 KB Output is correct
2 Correct 1037 ms 328520 KB Output is correct
3 Correct 1113 ms 342172 KB Output is correct
4 Correct 2131 ms 515104 KB Output is correct
5 Correct 3073 ms 481448 KB Output is correct
6 Correct 1041 ms 328484 KB Output is correct
7 Correct 625 ms 345664 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23636 KB Output is correct
2 Correct 262 ms 123188 KB Output is correct
3 Correct 237 ms 129984 KB Output is correct
4 Correct 100 ms 58912 KB Output is correct
5 Correct 90 ms 60900 KB Output is correct
6 Correct 318 ms 123756 KB Output is correct
7 Correct 287 ms 127220 KB Output is correct
8 Correct 111 ms 62772 KB Output is correct
9 Correct 115 ms 54476 KB Output is correct
10 Correct 103 ms 55324 KB Output is correct
11 Correct 301 ms 131364 KB Output is correct
12 Correct 392 ms 135964 KB Output is correct
13 Correct 217 ms 135124 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23636 KB Output is correct
2 Correct 262 ms 123188 KB Output is correct
3 Correct 237 ms 129984 KB Output is correct
4 Correct 100 ms 58912 KB Output is correct
5 Correct 90 ms 60900 KB Output is correct
6 Correct 318 ms 123756 KB Output is correct
7 Correct 287 ms 127220 KB Output is correct
8 Correct 111 ms 62772 KB Output is correct
9 Correct 115 ms 54476 KB Output is correct
10 Correct 103 ms 55324 KB Output is correct
11 Correct 301 ms 131364 KB Output is correct
12 Correct 392 ms 135964 KB Output is correct
13 Correct 217 ms 135124 KB Output is correct
14 Correct 13 ms 22740 KB Output is correct
15 Correct 169 ms 79788 KB Output is correct
16 Correct 270 ms 126788 KB Output is correct
17 Correct 126 ms 82252 KB Output is correct
18 Correct 128 ms 82284 KB Output is correct
19 Correct 297 ms 130696 KB Output is correct
20 Correct 127 ms 79432 KB Output is correct
21 Correct 145 ms 82500 KB Output is correct
22 Correct 182 ms 120412 KB Output is correct
23 Correct 285 ms 120176 KB Output is correct
24 Correct 318 ms 127740 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23636 KB Output is correct
2 Correct 262 ms 123188 KB Output is correct
3 Correct 237 ms 129984 KB Output is correct
4 Correct 100 ms 58912 KB Output is correct
5 Correct 90 ms 60900 KB Output is correct
6 Correct 318 ms 123756 KB Output is correct
7 Correct 287 ms 127220 KB Output is correct
8 Correct 111 ms 62772 KB Output is correct
9 Correct 115 ms 54476 KB Output is correct
10 Correct 103 ms 55324 KB Output is correct
11 Correct 301 ms 131364 KB Output is correct
12 Correct 392 ms 135964 KB Output is correct
13 Correct 217 ms 135124 KB Output is correct
14 Correct 13 ms 22740 KB Output is correct
15 Correct 169 ms 79788 KB Output is correct
16 Correct 270 ms 126788 KB Output is correct
17 Correct 126 ms 82252 KB Output is correct
18 Correct 128 ms 82284 KB Output is correct
19 Correct 297 ms 130696 KB Output is correct
20 Correct 127 ms 79432 KB Output is correct
21 Correct 145 ms 82500 KB Output is correct
22 Correct 182 ms 120412 KB Output is correct
23 Correct 285 ms 120176 KB Output is correct
24 Correct 318 ms 127740 KB Output is correct
25 Correct 228 ms 129128 KB Output is correct
26 Correct 268 ms 129496 KB Output is correct
27 Correct 113 ms 58148 KB Output is correct
28 Correct 120 ms 58128 KB Output is correct
29 Correct 333 ms 129824 KB Output is correct
30 Correct 107 ms 62628 KB Output is correct
31 Correct 103 ms 62672 KB Output is correct
32 Correct 238 ms 108140 KB Output is correct
33 Correct 376 ms 134072 KB Output is correct
34 Correct 467 ms 115644 KB Output is correct
35 Correct 328 ms 128756 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23856 KB Output is correct
2 Correct 1037 ms 328520 KB Output is correct
3 Correct 1113 ms 342172 KB Output is correct
4 Correct 2131 ms 515104 KB Output is correct
5 Correct 3073 ms 481448 KB Output is correct
6 Correct 1041 ms 328484 KB Output is correct
7 Correct 625 ms 345664 KB Output is correct
8 Correct 16 ms 23636 KB Output is correct
9 Correct 262 ms 123188 KB Output is correct
10 Correct 237 ms 129984 KB Output is correct
11 Correct 100 ms 58912 KB Output is correct
12 Correct 90 ms 60900 KB Output is correct
13 Correct 318 ms 123756 KB Output is correct
14 Correct 287 ms 127220 KB Output is correct
15 Correct 111 ms 62772 KB Output is correct
16 Correct 115 ms 54476 KB Output is correct
17 Correct 103 ms 55324 KB Output is correct
18 Correct 301 ms 131364 KB Output is correct
19 Correct 392 ms 135964 KB Output is correct
20 Correct 217 ms 135124 KB Output is correct
21 Correct 13 ms 22740 KB Output is correct
22 Correct 169 ms 79788 KB Output is correct
23 Correct 270 ms 126788 KB Output is correct
24 Correct 126 ms 82252 KB Output is correct
25 Correct 128 ms 82284 KB Output is correct
26 Correct 297 ms 130696 KB Output is correct
27 Correct 127 ms 79432 KB Output is correct
28 Correct 145 ms 82500 KB Output is correct
29 Correct 182 ms 120412 KB Output is correct
30 Correct 285 ms 120176 KB Output is correct
31 Correct 318 ms 127740 KB Output is correct
32 Correct 228 ms 129128 KB Output is correct
33 Correct 268 ms 129496 KB Output is correct
34 Correct 113 ms 58148 KB Output is correct
35 Correct 120 ms 58128 KB Output is correct
36 Correct 333 ms 129824 KB Output is correct
37 Correct 107 ms 62628 KB Output is correct
38 Correct 103 ms 62672 KB Output is correct
39 Correct 238 ms 108140 KB Output is correct
40 Correct 376 ms 134072 KB Output is correct
41 Correct 467 ms 115644 KB Output is correct
42 Correct 328 ms 128756 KB Output is correct
43 Correct 10 ms 20904 KB Output is correct
44 Correct 14 ms 23892 KB Output is correct
45 Correct 5861 ms 870536 KB Output is correct
46 Correct 2217 ms 312696 KB Output is correct
47 Correct 2466 ms 313004 KB Output is correct
48 Correct 4255 ms 905700 KB Output is correct
49 Correct 6234 ms 882148 KB Output is correct
50 Correct 1084 ms 337748 KB Output is correct
51 Correct 4396 ms 908536 KB Output is correct
52 Correct 1052 ms 335784 KB Output is correct
53 Correct 5045 ms 715780 KB Output is correct
54 Correct 2605 ms 907120 KB Output is correct
55 Correct 2159 ms 774496 KB Output is correct
56 Correct 6057 ms 877244 KB Output is correct
57 Correct 6022 ms 877996 KB Output is correct
58 Correct 6297 ms 887200 KB Output is correct
59 Correct 6305 ms 892456 KB Output is correct
60 Correct 5533 ms 610080 KB Output is correct
61 Correct 6098 ms 637624 KB Output is correct