oj.uz

답안 #499569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499569 2021-12-28T17:04:37 Z blue 던전 (IOI21_dungeons) C++17
100 / 100
 5299 ms 974012 KB 
#include "dungeons.h"
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;

const int maxN = 400'000;
const int logN = 25;
const int logS = 8;

int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;

int nxt[1+maxN][logS][logN];
int gain[1+maxN][logS][logN];
int min_change[1+maxN][logS][logN]; //i, k, e

const int B = 10;
const int logMX = 25;
long long powB[1+logMX];

vector<long long> winscore(1+maxN, 0LL);

void tle_assert(bool b)
{
    if(!b) while(1);
}

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);

    N = n;
    S = s;
    P = p;
    W = w;
    L = l;

    powB[0] = 1;
    for(int e = 1; e <= logMX; e++)
        powB[e] = B * powB[e-1];


    for(int i = 0; i <= N; i++)
    {
        for(int k = 0; k < logS; k++)
        {
            if(s[i] < powB[k])
            {
                nxt[i][k][0] = w[i];
                gain[i][k][0] = s[i];
                min_change[i][k][0] = powB[k+1] - gain[i][k][0];
            }
            else if(powB[k] <= s[i] && s[i] < powB[k+1])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = min(powB[k+1] - p[i], (long long)s[i]);
            }
            else if(powB[k] < s[i])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = powB[k+1] - gain[i][k][0];
            }
        }
    }

    for(int e = 1; e < logN; e++)
    {
        for(int i = 0; i <= N; i++)
        {
            for(int k = 0; k < logS; k++)
            {
                nxt[i][k][e] = nxt[ nxt[i][k][e-1] ][k][e-1];
                gain[i][k][e] = gain[i][k][e-1] + gain[ nxt[i][k][e-1] ][k][e-1];
                min_change[i][k][e] = min(min_change[i][k][e-1], min_change[ nxt[i][k][e-1] ][k][e-1] - gain[i][k][e-1]);
            }
        }
    }

    for(int i = N-1; i >= 0; i--)
        winscore[i] = winscore[ W[i] ] + S[i];
}

long long simulate(int x, int z)
{
    int X = x;
    long long Z = z;
    for(int k = 0; k < logS; k++)
    {
        for(int T = 1; T <= B-1; T++)
        {
            if(powB[k+1] <= Z) continue;

            for(int e = logN - 1; e >= 0; e--)
            {
                if(Z >= min_change[X][k][e]) continue;
                Z += gain[X][k][e];
                X = nxt[X][k][e];
            }

            if(Z >= S[X])
            {
                Z += S[X];
                X = W[X];
            }
            else
            {
                Z += P[X];
                X = L[X];
            }
        }
    }

    Z += winscore[X];

    return Z;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3440 KB Output is correct
3 Correct 7 ms 8180 KB Output is correct
4 Correct 282 ms 124236 KB Output is correct
5 Correct 6 ms 8196 KB Output is correct
6 Correct 282 ms 124252 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5836 KB Output is correct
2 Correct 3150 ms 966704 KB Output is correct
3 Correct 3290 ms 969248 KB Output is correct
4 Correct 3215 ms 970704 KB Output is correct
5 Correct 2472 ms 970756 KB Output is correct
6 Correct 3409 ms 969248 KB Output is correct
7 Correct 3151 ms 967416 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5892 KB Output is correct
2 Correct 409 ms 125632 KB Output is correct
3 Correct 374 ms 125712 KB Output is correct
4 Correct 439 ms 125196 KB Output is correct
5 Correct 441 ms 125020 KB Output is correct
6 Correct 438 ms 125288 KB Output is correct
7 Correct 422 ms 125268 KB Output is correct
8 Correct 571 ms 125028 KB Output is correct
9 Correct 574 ms 124980 KB Output is correct
10 Correct 582 ms 124884 KB Output is correct
11 Correct 734 ms 125172 KB Output is correct
12 Correct 995 ms 125276 KB Output is correct
13 Correct 749 ms 125236 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5892 KB Output is correct
2 Correct 409 ms 125632 KB Output is correct
3 Correct 374 ms 125712 KB Output is correct
4 Correct 439 ms 125196 KB Output is correct
5 Correct 441 ms 125020 KB Output is correct
6 Correct 438 ms 125288 KB Output is correct
7 Correct 422 ms 125268 KB Output is correct
8 Correct 571 ms 125028 KB Output is correct
9 Correct 574 ms 124980 KB Output is correct
10 Correct 582 ms 124884 KB Output is correct
11 Correct 734 ms 125172 KB Output is correct
12 Correct 995 ms 125276 KB Output is correct
13 Correct 749 ms 125236 KB Output is correct
14 Correct 7 ms 5900 KB Output is correct
15 Correct 378 ms 125412 KB Output is correct
16 Correct 433 ms 125772 KB Output is correct
17 Correct 455 ms 125116 KB Output is correct
18 Correct 443 ms 125216 KB Output is correct
19 Correct 463 ms 125268 KB Output is correct
20 Correct 525 ms 125008 KB Output is correct
21 Correct 538 ms 125032 KB Output is correct
22 Correct 715 ms 125140 KB Output is correct
23 Correct 784 ms 125168 KB Output is correct
24 Correct 903 ms 125264 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5892 KB Output is correct
2 Correct 409 ms 125632 KB Output is correct
3 Correct 374 ms 125712 KB Output is correct
4 Correct 439 ms 125196 KB Output is correct
5 Correct 441 ms 125020 KB Output is correct
6 Correct 438 ms 125288 KB Output is correct
7 Correct 422 ms 125268 KB Output is correct
8 Correct 571 ms 125028 KB Output is correct
9 Correct 574 ms 124980 KB Output is correct
10 Correct 582 ms 124884 KB Output is correct
11 Correct 734 ms 125172 KB Output is correct
12 Correct 995 ms 125276 KB Output is correct
13 Correct 749 ms 125236 KB Output is correct
14 Correct 7 ms 5900 KB Output is correct
15 Correct 378 ms 125412 KB Output is correct
16 Correct 433 ms 125772 KB Output is correct
17 Correct 455 ms 125116 KB Output is correct
18 Correct 443 ms 125216 KB Output is correct
19 Correct 463 ms 125268 KB Output is correct
20 Correct 525 ms 125008 KB Output is correct
21 Correct 538 ms 125032 KB Output is correct
22 Correct 715 ms 125140 KB Output is correct
23 Correct 784 ms 125168 KB Output is correct
24 Correct 903 ms 125264 KB Output is correct
25 Correct 324 ms 124648 KB Output is correct
26 Correct 450 ms 125648 KB Output is correct
27 Correct 397 ms 125040 KB Output is correct
28 Correct 386 ms 125212 KB Output is correct
29 Correct 441 ms 125524 KB Output is correct
30 Correct 577 ms 125260 KB Output is correct
31 Correct 600 ms 125004 KB Output is correct
32 Correct 697 ms 125156 KB Output is correct
33 Correct 897 ms 125220 KB Output is correct
34 Correct 1152 ms 125040 KB Output is correct
35 Correct 650 ms 125116 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5836 KB Output is correct
2 Correct 3150 ms 966704 KB Output is correct
3 Correct 3290 ms 969248 KB Output is correct
4 Correct 3215 ms 970704 KB Output is correct
5 Correct 2472 ms 970756 KB Output is correct
6 Correct 3409 ms 969248 KB Output is correct
7 Correct 3151 ms 967416 KB Output is correct
8 Correct 5 ms 5892 KB Output is correct
9 Correct 409 ms 125632 KB Output is correct
10 Correct 374 ms 125712 KB Output is correct
11 Correct 439 ms 125196 KB Output is correct
12 Correct 441 ms 125020 KB Output is correct
13 Correct 438 ms 125288 KB Output is correct
14 Correct 422 ms 125268 KB Output is correct
15 Correct 571 ms 125028 KB Output is correct
16 Correct 574 ms 124980 KB Output is correct
17 Correct 582 ms 124884 KB Output is correct
18 Correct 734 ms 125172 KB Output is correct
19 Correct 995 ms 125276 KB Output is correct
20 Correct 749 ms 125236 KB Output is correct
21 Correct 7 ms 5900 KB Output is correct
22 Correct 378 ms 125412 KB Output is correct
23 Correct 433 ms 125772 KB Output is correct
24 Correct 455 ms 125116 KB Output is correct
25 Correct 443 ms 125216 KB Output is correct
26 Correct 463 ms 125268 KB Output is correct
27 Correct 525 ms 125008 KB Output is correct
28 Correct 538 ms 125032 KB Output is correct
29 Correct 715 ms 125140 KB Output is correct
30 Correct 784 ms 125168 KB Output is correct
31 Correct 903 ms 125264 KB Output is correct
32 Correct 324 ms 124648 KB Output is correct
33 Correct 450 ms 125648 KB Output is correct
34 Correct 397 ms 125040 KB Output is correct
35 Correct 386 ms 125212 KB Output is correct
36 Correct 441 ms 125524 KB Output is correct
37 Correct 577 ms 125260 KB Output is correct
38 Correct 600 ms 125004 KB Output is correct
39 Correct 697 ms 125156 KB Output is correct
40 Correct 897 ms 125220 KB Output is correct
41 Correct 1152 ms 125040 KB Output is correct
42 Correct 650 ms 125116 KB Output is correct
43 Correct 2 ms 3444 KB Output is correct
44 Correct 6 ms 5820 KB Output is correct
45 Correct 3708 ms 974008 KB Output is correct
46 Correct 2781 ms 969460 KB Output is correct
47 Correct 2715 ms 969840 KB Output is correct
48 Correct 2510 ms 971960 KB Output is correct
49 Correct 3784 ms 974012 KB Output is correct
50 Correct 3089 ms 971760 KB Output is correct
51 Correct 2450 ms 972060 KB Output is correct
52 Correct 3228 ms 969652 KB Output is correct
53 Correct 5177 ms 970624 KB Output is correct
54 Correct 3666 ms 971536 KB Output is correct
55 Correct 4029 ms 970544 KB Output is correct
56 Correct 4918 ms 971412 KB Output is correct
57 Correct 4933 ms 971412 KB Output is correct
58 Correct 5151 ms 971320 KB Output is correct
59 Correct 5299 ms 971448 KB Output is correct
60 Correct 4621 ms 970836 KB Output is correct
61 Correct 4263 ms 970636 KB Output is correct