oj.uz

답안 #800455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800455 2023-08-01T15:06:16 Z MohamedAliSaidane 던전 (IOI21_dungeons) C++17
100 / 100
 6927 ms 1946880 KB 
#include <bits/stdc++.h>
//#include "dungeons.h"
using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int nax = 4e5 + 5;
const ll INF = 1e7;
const int LG = 24;
const int LG2 = 10;
const int b = 6;
int n;
vi S, P, W, L;

int sp[nax][LG2][LG];
ll mini[nax][LG2][LG];
ll ps[nax][LG2][LG];
ll POW[LG2];
int cor[(int)(INF + 1)];
void init(int N, vi s, vi p, vi w, vi l)
{
    n = N, S = s, P = p, W= w, L = l;
    S.pb(0);
    W.pb(n);
    POW[0] = 1ll;
    for(int i =1; i < LG2; i++)
        POW[i] = (POW[i - 1] * 1ll * b);
    for(int i = 1; i < b; i++)
        cor[i] = 0;
    for(int j = b; j <= INF; j++)
        cor[j] = cor[j/b] + 1;
    for(int i = 0; i <= n; i++)
    {
        for(int l = 0; l < LG2; l++)
        {
            if(S[i] <= POW[l])
            {
                sp[i][l][0] = W[i];
                mini[i][l][0] = INF * 1ll * INF;
                ps[i][l][0] = S[i];
            }
            else
            {
                sp[i][l][0] = L[i];
                mini[i][l][0] = S[i];
                ps[i][l][0] = P[i];
            }
        }
    }
    for(int j = 1; j < LG; j++)
    {
        for(int i = 0; i <= n; i++)
        {
            for(int l = 0; l < LG2; l++)
            {
                sp[i][l][j] = sp[sp[i][l][j - 1]][l][j - 1];
                mini[i][l][j] = min(mini[i][l][j - 1], mini[sp[i][l][j - 1]][l][j - 1] - ps[i][l][j -  1]);
                ps[i][l][j] = ps[i][l][j - 1] + ps[sp[i][l][j - 1]][l][j - 1];
            }
        }
    }
}
pair<int,ll> check(int i, ll z)
{
    ll delta = 0ll;
    int l = (z >= INF)? LG2 - 1: cor[z];
    //cout << '\t' <<  i << ' ' << z << ' ' << l << '\n';
    for(int j = LG - 1; j >= 0; j--)
    {
        bool cond = (mini[i][l][j] - delta <= z) || (sp[i][l][j] == n);
        if(!(cond))
        {
            delta += ps[i][l][j];
            i = sp[i][l][j];
        }
    }
    if(z + delta < mini[i][l][0])
    {
        delta += ps[i][l][0];
        i = sp[i][l][0];
    }
    return {i, delta};
}
ll simulate(int x, int Z)
{
    ll z = Z;
    while(x != n)
    {
       // cout << x << ' ' << z << '\n';
        pair<int,ll> u = check(x, z);
        x = u.ff;
        z += u.ss;
        z += S[x];
        x = W[x];
    }
    return z;
}
/*
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    /*
    int n, q;
    cin >> n >> q;
    vi s(n), p(n), w(n), l(n);
    for(int i = 0; i < n; i++)
        cin >> s[i];
    for(int i = 0; i < n; i++)
        cin >> p[i];
    for(int i =0 ;i < n; i++)
        cin >> w[i];
    for(int i = 0;i < n; i++)
        cin >> l[i];
    init(n, s, p, w, l);
    while(q--)
    {
        int x, z;
        cin >> x >> z;
        cout << simulate(x, z) << '\n';
    }


    init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
    cout << simulate(0, 1) << '\n';
    cout << simulate(2, 3) << '\n';


}
*/

Compilation message

dungeons.cpp:112:5: warning: "/*" within comment [-Wcomment]
  112 |     /*
      |

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 22 ms 39520 KB Output is correct
3 Correct 29 ms 48972 KB Output is correct
4 Correct 387 ms 277608 KB Output is correct
5 Correct 32 ms 49000 KB Output is correct
6 Correct 412 ms 277552 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 44200 KB Output is correct
2 Correct 3993 ms 1942072 KB Output is correct
3 Correct 4722 ms 1941812 KB Output is correct
4 Correct 3615 ms 1941288 KB Output is correct
5 Correct 2932 ms 1941032 KB Output is correct
6 Correct 3851 ms 1940408 KB Output is correct
7 Correct 3426 ms 1940384 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 44236 KB Output is correct
2 Correct 478 ms 279064 KB Output is correct
3 Correct 454 ms 279196 KB Output is correct
4 Correct 459 ms 278680 KB Output is correct
5 Correct 437 ms 278444 KB Output is correct
6 Correct 445 ms 278700 KB Output is correct
7 Correct 480 ms 278596 KB Output is correct
8 Correct 448 ms 278484 KB Output is correct
9 Correct 439 ms 278328 KB Output is correct
10 Correct 431 ms 278320 KB Output is correct
11 Correct 539 ms 278728 KB Output is correct
12 Correct 689 ms 278808 KB Output is correct
13 Correct 516 ms 278588 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 44236 KB Output is correct
2 Correct 478 ms 279064 KB Output is correct
3 Correct 454 ms 279196 KB Output is correct
4 Correct 459 ms 278680 KB Output is correct
5 Correct 437 ms 278444 KB Output is correct
6 Correct 445 ms 278700 KB Output is correct
7 Correct 480 ms 278596 KB Output is correct
8 Correct 448 ms 278484 KB Output is correct
9 Correct 439 ms 278328 KB Output is correct
10 Correct 431 ms 278320 KB Output is correct
11 Correct 539 ms 278728 KB Output is correct
12 Correct 689 ms 278808 KB Output is correct
13 Correct 516 ms 278588 KB Output is correct
14 Correct 31 ms 44224 KB Output is correct
15 Correct 450 ms 278848 KB Output is correct
16 Correct 481 ms 279056 KB Output is correct
17 Correct 457 ms 278580 KB Output is correct
18 Correct 475 ms 278612 KB Output is correct
19 Correct 485 ms 278700 KB Output is correct
20 Correct 558 ms 278448 KB Output is correct
21 Correct 466 ms 278600 KB Output is correct
22 Correct 467 ms 278568 KB Output is correct
23 Correct 557 ms 278696 KB Output is correct
24 Correct 701 ms 278696 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 44236 KB Output is correct
2 Correct 478 ms 279064 KB Output is correct
3 Correct 454 ms 279196 KB Output is correct
4 Correct 459 ms 278680 KB Output is correct
5 Correct 437 ms 278444 KB Output is correct
6 Correct 445 ms 278700 KB Output is correct
7 Correct 480 ms 278596 KB Output is correct
8 Correct 448 ms 278484 KB Output is correct
9 Correct 439 ms 278328 KB Output is correct
10 Correct 431 ms 278320 KB Output is correct
11 Correct 539 ms 278728 KB Output is correct
12 Correct 689 ms 278808 KB Output is correct
13 Correct 516 ms 278588 KB Output is correct
14 Correct 31 ms 44224 KB Output is correct
15 Correct 450 ms 278848 KB Output is correct
16 Correct 481 ms 279056 KB Output is correct
17 Correct 457 ms 278580 KB Output is correct
18 Correct 475 ms 278612 KB Output is correct
19 Correct 485 ms 278700 KB Output is correct
20 Correct 558 ms 278448 KB Output is correct
21 Correct 466 ms 278600 KB Output is correct
22 Correct 467 ms 278568 KB Output is correct
23 Correct 557 ms 278696 KB Output is correct
24 Correct 701 ms 278696 KB Output is correct
25 Correct 429 ms 277956 KB Output is correct
26 Correct 473 ms 279044 KB Output is correct
27 Correct 472 ms 278444 KB Output is correct
28 Correct 447 ms 278556 KB Output is correct
29 Correct 460 ms 278988 KB Output is correct
30 Correct 742 ms 278704 KB Output is correct
31 Correct 583 ms 278444 KB Output is correct
32 Correct 688 ms 278572 KB Output is correct
33 Correct 763 ms 278596 KB Output is correct
34 Correct 1043 ms 278484 KB Output is correct
35 Correct 609 ms 278544 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 44200 KB Output is correct
2 Correct 3993 ms 1942072 KB Output is correct
3 Correct 4722 ms 1941812 KB Output is correct
4 Correct 3615 ms 1941288 KB Output is correct
5 Correct 2932 ms 1941032 KB Output is correct
6 Correct 3851 ms 1940408 KB Output is correct
7 Correct 3426 ms 1940384 KB Output is correct
8 Correct 32 ms 44236 KB Output is correct
9 Correct 478 ms 279064 KB Output is correct
10 Correct 454 ms 279196 KB Output is correct
11 Correct 459 ms 278680 KB Output is correct
12 Correct 437 ms 278444 KB Output is correct
13 Correct 445 ms 278700 KB Output is correct
14 Correct 480 ms 278596 KB Output is correct
15 Correct 448 ms 278484 KB Output is correct
16 Correct 439 ms 278328 KB Output is correct
17 Correct 431 ms 278320 KB Output is correct
18 Correct 539 ms 278728 KB Output is correct
19 Correct 689 ms 278808 KB Output is correct
20 Correct 516 ms 278588 KB Output is correct
21 Correct 31 ms 44224 KB Output is correct
22 Correct 450 ms 278848 KB Output is correct
23 Correct 481 ms 279056 KB Output is correct
24 Correct 457 ms 278580 KB Output is correct
25 Correct 475 ms 278612 KB Output is correct
26 Correct 485 ms 278700 KB Output is correct
27 Correct 558 ms 278448 KB Output is correct
28 Correct 466 ms 278600 KB Output is correct
29 Correct 467 ms 278568 KB Output is correct
30 Correct 557 ms 278696 KB Output is correct
31 Correct 701 ms 278696 KB Output is correct
32 Correct 429 ms 277956 KB Output is correct
33 Correct 473 ms 279044 KB Output is correct
34 Correct 472 ms 278444 KB Output is correct
35 Correct 447 ms 278556 KB Output is correct
36 Correct 460 ms 278988 KB Output is correct
37 Correct 742 ms 278704 KB Output is correct
38 Correct 583 ms 278444 KB Output is correct
39 Correct 688 ms 278572 KB Output is correct
40 Correct 763 ms 278596 KB Output is correct
41 Correct 1043 ms 278484 KB Output is correct
42 Correct 609 ms 278544 KB Output is correct
43 Correct 22 ms 39480 KB Output is correct
44 Correct 27 ms 44184 KB Output is correct
45 Correct 4421 ms 1938864 KB Output is correct
46 Correct 3833 ms 1938740 KB Output is correct
47 Correct 3791 ms 1938484 KB Output is correct
48 Correct 3296 ms 1938352 KB Output is correct
49 Correct 4626 ms 1937968 KB Output is correct
50 Correct 3814 ms 1937768 KB Output is correct
51 Correct 3427 ms 1937716 KB Output is correct
52 Correct 3790 ms 1937724 KB Output is correct
53 Correct 6894 ms 1937812 KB Output is correct
54 Correct 4203 ms 1946824 KB Output is correct
55 Correct 4911 ms 1945884 KB Output is correct
56 Correct 5990 ms 1946552 KB Output is correct
57 Correct 6497 ms 1946680 KB Output is correct
58 Correct 6680 ms 1946624 KB Output is correct
59 Correct 6927 ms 1946880 KB Output is correct
60 Correct 5499 ms 1946008 KB Output is correct
61 Correct 4878 ms 1945956 KB Output is correct