oj.uz

답안 #919412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919412 2024-01-31T17:49:08 Z vjudge1 던전 (IOI21_dungeons) C++17
100 / 100
 6621 ms 1907216 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=10,sz=9;
const long long INF=1e18;
int 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){
    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 (nxt[x][0][0]!=-1){
        while (cur<ve.size()&&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;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (cur<ve.size()&&ve[cur]<=z)
      |                ~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 376916 KB Output is correct
2 Correct 89 ms 376888 KB Output is correct
3 Correct 106 ms 384352 KB Output is correct
4 Correct 527 ms 567748 KB Output is correct
5 Correct 88 ms 384380 KB Output is correct
6 Correct 502 ms 567616 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 380496 KB Output is correct
2 Correct 4658 ms 1902204 KB Output is correct
3 Correct 4742 ms 1902568 KB Output is correct
4 Correct 4532 ms 1903972 KB Output is correct
5 Correct 3763 ms 1903996 KB Output is correct
6 Correct 4492 ms 1902464 KB Output is correct
7 Correct 4320 ms 1900664 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 383064 KB Output is correct
2 Correct 533 ms 570732 KB Output is correct
3 Correct 571 ms 570856 KB Output is correct
4 Correct 454 ms 570348 KB Output is correct
5 Correct 433 ms 570220 KB Output is correct
6 Correct 542 ms 570476 KB Output is correct
7 Correct 536 ms 570480 KB Output is correct
8 Correct 458 ms 570220 KB Output is correct
9 Correct 337 ms 570220 KB Output is correct
10 Correct 478 ms 570096 KB Output is correct
11 Correct 534 ms 570448 KB Output is correct
12 Correct 797 ms 570840 KB Output is correct
13 Correct 681 ms 570476 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 383064 KB Output is correct
2 Correct 533 ms 570732 KB Output is correct
3 Correct 571 ms 570856 KB Output is correct
4 Correct 454 ms 570348 KB Output is correct
5 Correct 433 ms 570220 KB Output is correct
6 Correct 542 ms 570476 KB Output is correct
7 Correct 536 ms 570480 KB Output is correct
8 Correct 458 ms 570220 KB Output is correct
9 Correct 337 ms 570220 KB Output is correct
10 Correct 478 ms 570096 KB Output is correct
11 Correct 534 ms 570448 KB Output is correct
12 Correct 797 ms 570840 KB Output is correct
13 Correct 681 ms 570476 KB Output is correct
14 Correct 59 ms 383024 KB Output is correct
15 Correct 530 ms 570604 KB Output is correct
16 Correct 556 ms 570736 KB Output is correct
17 Correct 556 ms 570460 KB Output is correct
18 Correct 566 ms 570352 KB Output is correct
19 Correct 513 ms 573932 KB Output is correct
20 Correct 541 ms 573684 KB Output is correct
21 Correct 445 ms 573804 KB Output is correct
22 Correct 455 ms 573800 KB Output is correct
23 Correct 446 ms 574072 KB Output is correct
24 Correct 726 ms 573932 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 383064 KB Output is correct
2 Correct 533 ms 570732 KB Output is correct
3 Correct 571 ms 570856 KB Output is correct
4 Correct 454 ms 570348 KB Output is correct
5 Correct 433 ms 570220 KB Output is correct
6 Correct 542 ms 570476 KB Output is correct
7 Correct 536 ms 570480 KB Output is correct
8 Correct 458 ms 570220 KB Output is correct
9 Correct 337 ms 570220 KB Output is correct
10 Correct 478 ms 570096 KB Output is correct
11 Correct 534 ms 570448 KB Output is correct
12 Correct 797 ms 570840 KB Output is correct
13 Correct 681 ms 570476 KB Output is correct
14 Correct 59 ms 383024 KB Output is correct
15 Correct 530 ms 570604 KB Output is correct
16 Correct 556 ms 570736 KB Output is correct
17 Correct 556 ms 570460 KB Output is correct
18 Correct 566 ms 570352 KB Output is correct
19 Correct 513 ms 573932 KB Output is correct
20 Correct 541 ms 573684 KB Output is correct
21 Correct 445 ms 573804 KB Output is correct
22 Correct 455 ms 573800 KB Output is correct
23 Correct 446 ms 574072 KB Output is correct
24 Correct 726 ms 573932 KB Output is correct
25 Correct 400 ms 573252 KB Output is correct
26 Correct 467 ms 574192 KB Output is correct
27 Correct 426 ms 573676 KB Output is correct
28 Correct 423 ms 573760 KB Output is correct
29 Correct 471 ms 574340 KB Output is correct
30 Correct 551 ms 573936 KB Output is correct
31 Correct 512 ms 573680 KB Output is correct
32 Correct 614 ms 573812 KB Output is correct
33 Correct 1743 ms 573932 KB Output is correct
34 Correct 1786 ms 573804 KB Output is correct
35 Correct 754 ms 574024 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 380496 KB Output is correct
2 Correct 4658 ms 1902204 KB Output is correct
3 Correct 4742 ms 1902568 KB Output is correct
4 Correct 4532 ms 1903972 KB Output is correct
5 Correct 3763 ms 1903996 KB Output is correct
6 Correct 4492 ms 1902464 KB Output is correct
7 Correct 4320 ms 1900664 KB Output is correct
8 Correct 61 ms 383064 KB Output is correct
9 Correct 533 ms 570732 KB Output is correct
10 Correct 571 ms 570856 KB Output is correct
11 Correct 454 ms 570348 KB Output is correct
12 Correct 433 ms 570220 KB Output is correct
13 Correct 542 ms 570476 KB Output is correct
14 Correct 536 ms 570480 KB Output is correct
15 Correct 458 ms 570220 KB Output is correct
16 Correct 337 ms 570220 KB Output is correct
17 Correct 478 ms 570096 KB Output is correct
18 Correct 534 ms 570448 KB Output is correct
19 Correct 797 ms 570840 KB Output is correct
20 Correct 681 ms 570476 KB Output is correct
21 Correct 59 ms 383024 KB Output is correct
22 Correct 530 ms 570604 KB Output is correct
23 Correct 556 ms 570736 KB Output is correct
24 Correct 556 ms 570460 KB Output is correct
25 Correct 566 ms 570352 KB Output is correct
26 Correct 513 ms 573932 KB Output is correct
27 Correct 541 ms 573684 KB Output is correct
28 Correct 445 ms 573804 KB Output is correct
29 Correct 455 ms 573800 KB Output is correct
30 Correct 446 ms 574072 KB Output is correct
31 Correct 726 ms 573932 KB Output is correct
32 Correct 400 ms 573252 KB Output is correct
33 Correct 467 ms 574192 KB Output is correct
34 Correct 426 ms 573676 KB Output is correct
35 Correct 423 ms 573760 KB Output is correct
36 Correct 471 ms 574340 KB Output is correct
37 Correct 551 ms 573936 KB Output is correct
38 Correct 512 ms 573680 KB Output is correct
39 Correct 614 ms 573812 KB Output is correct
40 Correct 1743 ms 573932 KB Output is correct
41 Correct 1786 ms 573804 KB Output is correct
42 Correct 754 ms 574024 KB Output is correct
43 Correct 53 ms 380752 KB Output is correct
44 Correct 56 ms 383212 KB Output is correct
45 Correct 3852 ms 1907216 KB Output is correct
46 Correct 3512 ms 1902588 KB Output is correct
47 Correct 3586 ms 1902972 KB Output is correct
48 Correct 3528 ms 1905160 KB Output is correct
49 Correct 3779 ms 1907208 KB Output is correct
50 Correct 3683 ms 1904784 KB Output is correct
51 Correct 3286 ms 1905160 KB Output is correct
52 Correct 3691 ms 1902928 KB Output is correct
53 Correct 5502 ms 1903612 KB Output is correct
54 Correct 5676 ms 1904764 KB Output is correct
55 Correct 5743 ms 1903492 KB Output is correct
56 Correct 5904 ms 1904580 KB Output is correct
57 Correct 5829 ms 1904388 KB Output is correct
58 Correct 6621 ms 1904516 KB Output is correct
59 Correct 6548 ms 1904648 KB Output is correct
60 Correct 6269 ms 1903876 KB Output is correct
61 Correct 5761 ms 1904000 KB Output is correct