oj.uz

답안 #929108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
929108 2024-02-17T17:26:18 Z abcvuitunggio 던전 (IOI21_dungeons) C++17
100 / 100
 5298 ms 1906300 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=6,sz=9;
const long long INF=1e18;
int N,nxt[400001][24][sz+1];
long long mx[400001][24],mn[400001][24][sz],sum[400001][24][sz+1];
vector <int> S,P,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    N=n,S=s,P=p;
    for (int i=1;i<sz;i++)
        ve.push_back(ve.back()*base);
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        for (int j=0;j<sz;j++)
            if (s[i]<=ve[j]){
                nxt[i][0][j]=w[i];
                sum[i][0][j]=s[i];
                mn[i][0][j]=INF;
            }
            else{
                nxt[i][0][j]=l[i];
                sum[i][0][j]=p[i];
                mn[i][0][j]=s[i];
            }
        nxt[i][0][sz]=w[i];
        mx[i][0]=sum[i][0][sz]=s[i];
    }
    for (int j=1;j<24;j++){
        for (int i=0;i<n;i++)
            for (int k=0;k<=sz;k++){
                if (nxt[i][j-1][k]==-1)
                    continue;
                int u=nxt[i][j-1][k];
                nxt[i][j][k]=nxt[u][j-1][k];
                if (k<sz)
                    mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-sum[i][j-1][k]);
                else
                    mx[i][j]=max(mx[i][j-1],mx[u][j-1]-sum[i][j-1][k]);
                sum[i][j][k]=sum[i][j-1][k]+sum[u][j-1][k];
            }
    }
}
long long simulate(int x, int Z){
    int b=0,cur=0;
    long long z=Z;
    while (x<N){
        while (cur<sz&&ve[cur]<=z)
            cur++;
        int j=(b?cur-1:sz);
        for (int i=23;i>=0;i--)
            if (nxt[x][i][j]!=-1)
                if ((b&&z<mn[x][i][j])||(!b&&z>=mx[x][i])){
                    z+=sum[x][i][j];
                    x=nxt[x][i][j];
                }
        b^=1;
    }
    return z;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 376028 KB Output is correct
2 Correct 161 ms 376196 KB Output is correct
3 Correct 155 ms 383572 KB Output is correct
4 Correct 487 ms 567124 KB Output is correct
5 Correct 158 ms 383572 KB Output is correct
6 Correct 487 ms 566668 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 383040 KB Output is correct
2 Correct 3406 ms 1902264 KB Output is correct
3 Correct 3469 ms 1902444 KB Output is correct
4 Correct 3875 ms 1903876 KB Output is correct
5 Correct 2907 ms 1902456 KB Output is correct
6 Correct 3561 ms 1895548 KB Output is correct
7 Correct 3329 ms 1895548 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 383060 KB Output is correct
2 Correct 347 ms 572640 KB Output is correct
3 Correct 521 ms 566608 KB Output is correct
4 Correct 478 ms 566544 KB Output is correct
5 Correct 456 ms 566608 KB Output is correct
6 Correct 606 ms 567344 KB Output is correct
7 Correct 466 ms 570944 KB Output is correct
8 Correct 455 ms 566792 KB Output is correct
9 Correct 400 ms 566788 KB Output is correct
10 Correct 483 ms 566792 KB Output is correct
11 Correct 518 ms 566792 KB Output is correct
12 Correct 539 ms 572760 KB Output is correct
13 Correct 518 ms 567488 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 383060 KB Output is correct
2 Correct 347 ms 572640 KB Output is correct
3 Correct 521 ms 566608 KB Output is correct
4 Correct 478 ms 566544 KB Output is correct
5 Correct 456 ms 566608 KB Output is correct
6 Correct 606 ms 567344 KB Output is correct
7 Correct 466 ms 570944 KB Output is correct
8 Correct 455 ms 566792 KB Output is correct
9 Correct 400 ms 566788 KB Output is correct
10 Correct 483 ms 566792 KB Output is correct
11 Correct 518 ms 566792 KB Output is correct
12 Correct 539 ms 572760 KB Output is correct
13 Correct 518 ms 567488 KB Output is correct
14 Correct 65 ms 380668 KB Output is correct
15 Correct 440 ms 567376 KB Output is correct
16 Correct 467 ms 567560 KB Output is correct
17 Correct 453 ms 567380 KB Output is correct
18 Correct 393 ms 572756 KB Output is correct
19 Correct 509 ms 567584 KB Output is correct
20 Correct 573 ms 567484 KB Output is correct
21 Correct 553 ms 567632 KB Output is correct
22 Correct 353 ms 572752 KB Output is correct
23 Correct 551 ms 566580 KB Output is correct
24 Correct 754 ms 566796 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 383060 KB Output is correct
2 Correct 347 ms 572640 KB Output is correct
3 Correct 521 ms 566608 KB Output is correct
4 Correct 478 ms 566544 KB Output is correct
5 Correct 456 ms 566608 KB Output is correct
6 Correct 606 ms 567344 KB Output is correct
7 Correct 466 ms 570944 KB Output is correct
8 Correct 455 ms 566792 KB Output is correct
9 Correct 400 ms 566788 KB Output is correct
10 Correct 483 ms 566792 KB Output is correct
11 Correct 518 ms 566792 KB Output is correct
12 Correct 539 ms 572760 KB Output is correct
13 Correct 518 ms 567488 KB Output is correct
14 Correct 65 ms 380668 KB Output is correct
15 Correct 440 ms 567376 KB Output is correct
16 Correct 467 ms 567560 KB Output is correct
17 Correct 453 ms 567380 KB Output is correct
18 Correct 393 ms 572756 KB Output is correct
19 Correct 509 ms 567584 KB Output is correct
20 Correct 573 ms 567484 KB Output is correct
21 Correct 553 ms 567632 KB Output is correct
22 Correct 353 ms 572752 KB Output is correct
23 Correct 551 ms 566580 KB Output is correct
24 Correct 754 ms 566796 KB Output is correct
25 Correct 494 ms 566000 KB Output is correct
26 Correct 578 ms 567484 KB Output is correct
27 Correct 352 ms 572660 KB Output is correct
28 Correct 513 ms 567736 KB Output is correct
29 Correct 518 ms 567532 KB Output is correct
30 Correct 646 ms 567636 KB Output is correct
31 Correct 609 ms 570704 KB Output is correct
32 Correct 745 ms 566796 KB Output is correct
33 Correct 1373 ms 567376 KB Output is correct
34 Correct 1379 ms 572500 KB Output is correct
35 Correct 598 ms 572672 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 383040 KB Output is correct
2 Correct 3406 ms 1902264 KB Output is correct
3 Correct 3469 ms 1902444 KB Output is correct
4 Correct 3875 ms 1903876 KB Output is correct
5 Correct 2907 ms 1902456 KB Output is correct
6 Correct 3561 ms 1895548 KB Output is correct
7 Correct 3329 ms 1895548 KB Output is correct
8 Correct 62 ms 383060 KB Output is correct
9 Correct 347 ms 572640 KB Output is correct
10 Correct 521 ms 566608 KB Output is correct
11 Correct 478 ms 566544 KB Output is correct
12 Correct 456 ms 566608 KB Output is correct
13 Correct 606 ms 567344 KB Output is correct
14 Correct 466 ms 570944 KB Output is correct
15 Correct 455 ms 566792 KB Output is correct
16 Correct 400 ms 566788 KB Output is correct
17 Correct 483 ms 566792 KB Output is correct
18 Correct 518 ms 566792 KB Output is correct
19 Correct 539 ms 572760 KB Output is correct
20 Correct 518 ms 567488 KB Output is correct
21 Correct 65 ms 380668 KB Output is correct
22 Correct 440 ms 567376 KB Output is correct
23 Correct 467 ms 567560 KB Output is correct
24 Correct 453 ms 567380 KB Output is correct
25 Correct 393 ms 572756 KB Output is correct
26 Correct 509 ms 567584 KB Output is correct
27 Correct 573 ms 567484 KB Output is correct
28 Correct 553 ms 567632 KB Output is correct
29 Correct 353 ms 572752 KB Output is correct
30 Correct 551 ms 566580 KB Output is correct
31 Correct 754 ms 566796 KB Output is correct
32 Correct 494 ms 566000 KB Output is correct
33 Correct 578 ms 567484 KB Output is correct
34 Correct 352 ms 572660 KB Output is correct
35 Correct 513 ms 567736 KB Output is correct
36 Correct 518 ms 567532 KB Output is correct
37 Correct 646 ms 567636 KB Output is correct
38 Correct 609 ms 570704 KB Output is correct
39 Correct 745 ms 566796 KB Output is correct
40 Correct 1373 ms 567376 KB Output is correct
41 Correct 1379 ms 572500 KB Output is correct
42 Correct 598 ms 572672 KB Output is correct
43 Correct 44 ms 380928 KB Output is correct
44 Correct 47 ms 382984 KB Output is correct
45 Correct 3381 ms 1895564 KB Output is correct
46 Correct 3251 ms 1901696 KB Output is correct
47 Correct 3502 ms 1901948 KB Output is correct
48 Correct 2873 ms 1903484 KB Output is correct
49 Correct 3673 ms 1906300 KB Output is correct
50 Correct 3883 ms 1904512 KB Output is correct
51 Correct 2742 ms 1904508 KB Output is correct
52 Correct 3210 ms 1902832 KB Output is correct
53 Correct 5298 ms 1902396 KB Output is correct
54 Correct 4280 ms 1904752 KB Output is correct
55 Correct 4339 ms 1903724 KB Output is correct
56 Correct 4815 ms 1904368 KB Output is correct
57 Correct 4954 ms 1904468 KB Output is correct
58 Correct 5212 ms 1897500 KB Output is correct
59 Correct 5186 ms 1904612 KB Output is correct
60 Correct 4479 ms 1904016 KB Output is correct
61 Correct 4003 ms 1903708 KB Output is correct