oj.uz

Submission #827643

# Submission time Handle Problem Language Result Execution time Memory
827643 2023-08-16T15:39:11 Z TahirAliyev Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2365 ms 1741044 KB 
#pragma GCC optimize("O3")
#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, ll>
const ll oo = 1e18;

const int MAX = 400004, LOGMAX = 26;

const int logStart = 12, INC = 2;

int N;
vector<ll> S;
vector <int> st, P, W, L;

struct g{
    array<ll, 3> par[LOGMAX][MAX];
    void init(){
        for (int j = 1; j < LOGMAX; j++)
        {
            for (int i = 0; i <= N; i++)
            {
                int m = par[j - 1][i][0];
                par[j][i][0] = par[j - 1][m][0];
                par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
                par[j][i][2] = max(par[j - 1][i][2], par[j - 1][i][1] + par[j - 1][m][2]);
            }
        }
    }
    pii lift(int u, ll s, ll t){
        if(u == N || s >= t){
            return {u, s};
        }
        
        ll curs = s;
        int v = u;
        for (int j = LOGMAX - 1; j >= 0 && curs < t && v != N; j--)
        {
            if(curs + par[j][v][2] < 0){
                curs += par[j][v][1];
                v = par[j][v][0];
            }
        }
        if(v == N) return {v, curs};
        if(st[v] <= curs){
            return make_pair(W[v], st[v] + curs);
        }
        else{
            return make_pair(L[v], P[v] + curs);
        }
    }
};


g G[(LOGMAX - logStart) / INC];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n;
    st = s;
    P = p;
    W = w;
    L = l;
    for (int i = logStart; i < LOGMAX; i += INC)
    {
        S.push_back(1ll << i);
    }

    for (int j = 0; j < S.size(); j++)
    {
        for (int i = 0; i < n; i++)
        {
            if(s[i] <= S[j]){
                G[j].par[0][i] = {w[i], s[i], -oo};
            }
            else{
                G[j].par[0][i] = {l[i], p[i], -s[i]};
            }
        }
    }
    
    for (int j = 0; j < S.size(); j++)
    {
        G[j].par[0][n] = {n, 0, -oo};
        G[j].init();
    }
    
    S.push_back(oo);
}

ll simulate(int x, int z) {
    ll X = x, Z = z;
    while(Z < (1 << logStart) && X != N){
        if(Z >= st[X]){
            Z += st[X];
            X = W[X];
        }
        else{
            Z += P[X];
            X = L[X];
        }
    }
	for (int i = 0; i < S.size() - 1; i++)
    {
        while(Z < S[i + 1] && X != N){
            pii a = G[i].lift(X, Z, S[i + 1]);
            X = a.first, Z = a.second;
        }
    }
    return Z;
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int j = 0; j < S.size(); j++)
      |                     ~~^~~~~~~~~~
dungeons.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int j = 0; j < S.size(); j++)
      |                     ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 0; i < S.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 5 ms 10324 KB Output is correct
4 Correct 104 ms 217780 KB Output is correct
5 Correct 5 ms 10324 KB Output is correct
6 Correct 107 ms 217676 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 865 ms 1729412 KB Output is correct
3 Correct 831 ms 1729828 KB Output is correct
4 Correct 808 ms 1729872 KB Output is correct
5 Correct 824 ms 1729840 KB Output is correct
6 Correct 910 ms 1729788 KB Output is correct
7 Correct 987 ms 1729860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 140 ms 219000 KB Output is correct
3 Correct 163 ms 219004 KB Output is correct
4 Correct 122 ms 218832 KB Output is correct
5 Correct 136 ms 218896 KB Output is correct
6 Correct 173 ms 218936 KB Output is correct
7 Correct 407 ms 218912 KB Output is correct
8 Correct 144 ms 218920 KB Output is correct
9 Correct 126 ms 218992 KB Output is correct
10 Correct 211 ms 218828 KB Output is correct
11 Correct 1742 ms 218848 KB Output is correct
12 Correct 1825 ms 218864 KB Output is correct
13 Correct 659 ms 218836 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 140 ms 219000 KB Output is correct
3 Correct 163 ms 219004 KB Output is correct
4 Correct 122 ms 218832 KB Output is correct
5 Correct 136 ms 218896 KB Output is correct
6 Correct 173 ms 218936 KB Output is correct
7 Correct 407 ms 218912 KB Output is correct
8 Correct 144 ms 218920 KB Output is correct
9 Correct 126 ms 218992 KB Output is correct
10 Correct 211 ms 218828 KB Output is correct
11 Correct 1742 ms 218848 KB Output is correct
12 Correct 1825 ms 218864 KB Output is correct
13 Correct 659 ms 218836 KB Output is correct
14 Correct 3 ms 6100 KB Output is correct
15 Correct 145 ms 218908 KB Output is correct
16 Correct 173 ms 218916 KB Output is correct
17 Correct 128 ms 218700 KB Output is correct
18 Correct 151 ms 218716 KB Output is correct
19 Correct 231 ms 218900 KB Output is correct
20 Correct 176 ms 218852 KB Output is correct
21 Correct 172 ms 218880 KB Output is correct
22 Correct 720 ms 218932 KB Output is correct
23 Correct 1790 ms 218904 KB Output is correct
24 Correct 626 ms 218880 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 140 ms 219000 KB Output is correct
3 Correct 163 ms 219004 KB Output is correct
4 Correct 122 ms 218832 KB Output is correct
5 Correct 136 ms 218896 KB Output is correct
6 Correct 173 ms 218936 KB Output is correct
7 Correct 407 ms 218912 KB Output is correct
8 Correct 144 ms 218920 KB Output is correct
9 Correct 126 ms 218992 KB Output is correct
10 Correct 211 ms 218828 KB Output is correct
11 Correct 1742 ms 218848 KB Output is correct
12 Correct 1825 ms 218864 KB Output is correct
13 Correct 659 ms 218836 KB Output is correct
14 Correct 3 ms 6100 KB Output is correct
15 Correct 145 ms 218908 KB Output is correct
16 Correct 173 ms 218916 KB Output is correct
17 Correct 128 ms 218700 KB Output is correct
18 Correct 151 ms 218716 KB Output is correct
19 Correct 231 ms 218900 KB Output is correct
20 Correct 176 ms 218852 KB Output is correct
21 Correct 172 ms 218880 KB Output is correct
22 Correct 720 ms 218932 KB Output is correct
23 Correct 1790 ms 218904 KB Output is correct
24 Correct 626 ms 218880 KB Output is correct
25 Correct 119 ms 218212 KB Output is correct
26 Correct 176 ms 218976 KB Output is correct
27 Correct 150 ms 218828 KB Output is correct
28 Correct 152 ms 218724 KB Output is correct
29 Correct 207 ms 218992 KB Output is correct
30 Correct 218 ms 218788 KB Output is correct
31 Correct 216 ms 218864 KB Output is correct
32 Correct 468 ms 219100 KB Output is correct
33 Correct 516 ms 218812 KB Output is correct
34 Correct 1014 ms 218776 KB Output is correct
35 Correct 440 ms 218936 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 865 ms 1729412 KB Output is correct
3 Correct 831 ms 1729828 KB Output is correct
4 Correct 808 ms 1729872 KB Output is correct
5 Correct 824 ms 1729840 KB Output is correct
6 Correct 910 ms 1729788 KB Output is correct
7 Correct 987 ms 1729860 KB Output is correct
8 Correct 3 ms 6100 KB Output is correct
9 Correct 140 ms 219000 KB Output is correct
10 Correct 163 ms 219004 KB Output is correct
11 Correct 122 ms 218832 KB Output is correct
12 Correct 136 ms 218896 KB Output is correct
13 Correct 173 ms 218936 KB Output is correct
14 Correct 407 ms 218912 KB Output is correct
15 Correct 144 ms 218920 KB Output is correct
16 Correct 126 ms 218992 KB Output is correct
17 Correct 211 ms 218828 KB Output is correct
18 Correct 1742 ms 218848 KB Output is correct
19 Correct 1825 ms 218864 KB Output is correct
20 Correct 659 ms 218836 KB Output is correct
21 Correct 3 ms 6100 KB Output is correct
22 Correct 145 ms 218908 KB Output is correct
23 Correct 173 ms 218916 KB Output is correct
24 Correct 128 ms 218700 KB Output is correct
25 Correct 151 ms 218716 KB Output is correct
26 Correct 231 ms 218900 KB Output is correct
27 Correct 176 ms 218852 KB Output is correct
28 Correct 172 ms 218880 KB Output is correct
29 Correct 720 ms 218932 KB Output is correct
30 Correct 1790 ms 218904 KB Output is correct
31 Correct 626 ms 218880 KB Output is correct
32 Correct 119 ms 218212 KB Output is correct
33 Correct 176 ms 218976 KB Output is correct
34 Correct 150 ms 218828 KB Output is correct
35 Correct 152 ms 218724 KB Output is correct
36 Correct 207 ms 218992 KB Output is correct
37 Correct 218 ms 218788 KB Output is correct
38 Correct 216 ms 218864 KB Output is correct
39 Correct 468 ms 219100 KB Output is correct
40 Correct 516 ms 218812 KB Output is correct
41 Correct 1014 ms 218776 KB Output is correct
42 Correct 440 ms 218936 KB Output is correct
43 Correct 1 ms 1748 KB Output is correct
44 Correct 3 ms 6100 KB Output is correct
45 Correct 1010 ms 1730140 KB Output is correct
46 Correct 851 ms 1730952 KB Output is correct
47 Correct 864 ms 1731012 KB Output is correct
48 Correct 861 ms 1730208 KB Output is correct
49 Correct 1157 ms 1741044 KB Output is correct
50 Correct 939 ms 1738588 KB Output is correct
51 Correct 836 ms 1738992 KB Output is correct
52 Correct 953 ms 1736656 KB Output is correct
53 Correct 2176 ms 1736460 KB Output is correct
54 Correct 1667 ms 1735764 KB Output is correct
55 Correct 2237 ms 1735260 KB Output is correct
56 Correct 2365 ms 1734488 KB Output is correct
57 Correct 1974 ms 1738352 KB Output is correct
58 Correct 2123 ms 1738416 KB Output is correct
59 Correct 1935 ms 1738564 KB Output is correct
60 Correct 1913 ms 1737896 KB Output is correct
61 Correct 1821 ms 1737684 KB Output is correct