oj.uz

답안 #826264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826264 2023-08-15T11:41:50 Z TheSahib 던전 (IOI21_dungeons) C++17
100 / 100
 2436 ms 1676772 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 = 1e9 + 9;
const int MAX = 500005;
const int LOGMAX = 25;
const int liftMAX = 24;
const int startLog = 12;


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

struct G{
    array<ll, 3> par[liftMAX + 1][MAX];
    void preCalc(){
        for (int j = 1; j <= liftMAX; 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][m][2] + par[j - 1][i][1]);
            }
        }
    }
    pii lift(ll start, ll target, int v){
        if(start >= target || v == n) return {v, start};
        for(int j = liftMAX; j >= 0 && v != n && start < target; --j){
            if(start + par[j][v][2] < 0){
                start = start + par[j][v][1];
                v = par[j][v][0];
            }
        }
        if(v == n){
            return {n, start};
        }
        if(start >= S[v]){
            start += S[v];
            v = W[v];
        }
        else{
            start += P[v];
            v = L[v];
        }
        return {v, start};
    }
};

vector<ll> v;
G gs[(LOGMAX - startLog + 2) / 2];

void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    n = N;
    S = s;
    P = p;
    W = w;
    L = l;

    for(int i = startLog; i < LOGMAX; i += 2){
        v.push_back((1 << i));
    }
    
    for (int i = 0; i < v.size(); i++)
    {
        for(int j = 0; j <= N; ++j){
            if(j == N){
                gs[i].par[0][j] = {N, 0, -oo * oo};
                continue;
            }
            if(s[j] > v[i]){
                gs[i].par[0][j] = {l[j], p[j], p[j] - s[j]};
            }
            else{
                gs[i].par[0][j] = {w[j], s[j], -oo * oo};
            }
        }
        gs[i].preCalc();
    }
    v.push_back(oo * oo);
    return;
}

ll simulate(int x, int z) {
    ll u = x;
    ll s = z;
    while(s < (1 << startLog) && u != n){
        if(s >= S[u]){
            s += S[u];
            u = W[u];
        }
        else{
            s += P[u];
            u = L[u];
        }
    }
	for (int i = 0; i < v.size() - 1; i++)
    {
        while(u != n && s < v[i + 1]){
            pii p = gs[i].lift(s, v[i + 1], u);
            u = p.first;
            s = p.second;
        }
    }
    return s;
}

Compilation message

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

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 7 ms 9892 KB Output is correct
4 Correct 111 ms 209424 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 97 ms 209520 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 943 ms 1665052 KB Output is correct
3 Correct 922 ms 1671904 KB Output is correct
4 Correct 810 ms 1673592 KB Output is correct
5 Correct 962 ms 1673572 KB Output is correct
6 Correct 984 ms 1672124 KB Output is correct
7 Correct 1039 ms 1670152 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 159 ms 210904 KB Output is correct
3 Correct 187 ms 210852 KB Output is correct
4 Correct 129 ms 210824 KB Output is correct
5 Correct 154 ms 210632 KB Output is correct
6 Correct 185 ms 210776 KB Output is correct
7 Correct 412 ms 210740 KB Output is correct
8 Correct 157 ms 210892 KB Output is correct
9 Correct 132 ms 210780 KB Output is correct
10 Correct 222 ms 210640 KB Output is correct
11 Correct 1759 ms 210724 KB Output is correct
12 Correct 1810 ms 210724 KB Output is correct
13 Correct 683 ms 210756 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 159 ms 210904 KB Output is correct
3 Correct 187 ms 210852 KB Output is correct
4 Correct 129 ms 210824 KB Output is correct
5 Correct 154 ms 210632 KB Output is correct
6 Correct 185 ms 210776 KB Output is correct
7 Correct 412 ms 210740 KB Output is correct
8 Correct 157 ms 210892 KB Output is correct
9 Correct 132 ms 210780 KB Output is correct
10 Correct 222 ms 210640 KB Output is correct
11 Correct 1759 ms 210724 KB Output is correct
12 Correct 1810 ms 210724 KB Output is correct
13 Correct 683 ms 210756 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 151 ms 210740 KB Output is correct
16 Correct 181 ms 210748 KB Output is correct
17 Correct 138 ms 210652 KB Output is correct
18 Correct 148 ms 210784 KB Output is correct
19 Correct 219 ms 211004 KB Output is correct
20 Correct 186 ms 210684 KB Output is correct
21 Correct 160 ms 210688 KB Output is correct
22 Correct 732 ms 210760 KB Output is correct
23 Correct 1929 ms 210724 KB Output is correct
24 Correct 684 ms 210772 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 159 ms 210904 KB Output is correct
3 Correct 187 ms 210852 KB Output is correct
4 Correct 129 ms 210824 KB Output is correct
5 Correct 154 ms 210632 KB Output is correct
6 Correct 185 ms 210776 KB Output is correct
7 Correct 412 ms 210740 KB Output is correct
8 Correct 157 ms 210892 KB Output is correct
9 Correct 132 ms 210780 KB Output is correct
10 Correct 222 ms 210640 KB Output is correct
11 Correct 1759 ms 210724 KB Output is correct
12 Correct 1810 ms 210724 KB Output is correct
13 Correct 683 ms 210756 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 151 ms 210740 KB Output is correct
16 Correct 181 ms 210748 KB Output is correct
17 Correct 138 ms 210652 KB Output is correct
18 Correct 148 ms 210784 KB Output is correct
19 Correct 219 ms 211004 KB Output is correct
20 Correct 186 ms 210684 KB Output is correct
21 Correct 160 ms 210688 KB Output is correct
22 Correct 732 ms 210760 KB Output is correct
23 Correct 1929 ms 210724 KB Output is correct
24 Correct 684 ms 210772 KB Output is correct
25 Correct 132 ms 210104 KB Output is correct
26 Correct 199 ms 210704 KB Output is correct
27 Correct 171 ms 210640 KB Output is correct
28 Correct 164 ms 210692 KB Output is correct
29 Correct 204 ms 210828 KB Output is correct
30 Correct 220 ms 210680 KB Output is correct
31 Correct 225 ms 210668 KB Output is correct
32 Correct 525 ms 210568 KB Output is correct
33 Correct 498 ms 210740 KB Output is correct
34 Correct 1225 ms 210776 KB Output is correct
35 Correct 525 ms 210860 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 943 ms 1665052 KB Output is correct
3 Correct 922 ms 1671904 KB Output is correct
4 Correct 810 ms 1673592 KB Output is correct
5 Correct 962 ms 1673572 KB Output is correct
6 Correct 984 ms 1672124 KB Output is correct
7 Correct 1039 ms 1670152 KB Output is correct
8 Correct 3 ms 5844 KB Output is correct
9 Correct 159 ms 210904 KB Output is correct
10 Correct 187 ms 210852 KB Output is correct
11 Correct 129 ms 210824 KB Output is correct
12 Correct 154 ms 210632 KB Output is correct
13 Correct 185 ms 210776 KB Output is correct
14 Correct 412 ms 210740 KB Output is correct
15 Correct 157 ms 210892 KB Output is correct
16 Correct 132 ms 210780 KB Output is correct
17 Correct 222 ms 210640 KB Output is correct
18 Correct 1759 ms 210724 KB Output is correct
19 Correct 1810 ms 210724 KB Output is correct
20 Correct 683 ms 210756 KB Output is correct
21 Correct 3 ms 5844 KB Output is correct
22 Correct 151 ms 210740 KB Output is correct
23 Correct 181 ms 210748 KB Output is correct
24 Correct 138 ms 210652 KB Output is correct
25 Correct 148 ms 210784 KB Output is correct
26 Correct 219 ms 211004 KB Output is correct
27 Correct 186 ms 210684 KB Output is correct
28 Correct 160 ms 210688 KB Output is correct
29 Correct 732 ms 210760 KB Output is correct
30 Correct 1929 ms 210724 KB Output is correct
31 Correct 684 ms 210772 KB Output is correct
32 Correct 132 ms 210104 KB Output is correct
33 Correct 199 ms 210704 KB Output is correct
34 Correct 171 ms 210640 KB Output is correct
35 Correct 164 ms 210692 KB Output is correct
36 Correct 204 ms 210828 KB Output is correct
37 Correct 220 ms 210680 KB Output is correct
38 Correct 225 ms 210668 KB Output is correct
39 Correct 525 ms 210568 KB Output is correct
40 Correct 498 ms 210740 KB Output is correct
41 Correct 1225 ms 210776 KB Output is correct
42 Correct 525 ms 210860 KB Output is correct
43 Correct 1 ms 1620 KB Output is correct
44 Correct 3 ms 5888 KB Output is correct
45 Correct 1079 ms 1676772 KB Output is correct
46 Correct 861 ms 1672088 KB Output is correct
47 Correct 954 ms 1672508 KB Output is correct
48 Correct 892 ms 1674772 KB Output is correct
49 Correct 1074 ms 1676760 KB Output is correct
50 Correct 917 ms 1674316 KB Output is correct
51 Correct 872 ms 1674704 KB Output is correct
52 Correct 1056 ms 1672456 KB Output is correct
53 Correct 1846 ms 1673128 KB Output is correct
54 Correct 1670 ms 1674124 KB Output is correct
55 Correct 2436 ms 1673380 KB Output is correct
56 Correct 1826 ms 1673840 KB Output is correct
57 Correct 1810 ms 1674064 KB Output is correct
58 Correct 1980 ms 1674068 KB Output is correct
59 Correct 1903 ms 1674160 KB Output is correct
60 Correct 2057 ms 1673396 KB Output is correct
61 Correct 1907 ms 1673276 KB Output is correct