oj.uz

Submission #790386

# Submission time Handle Problem Language Result Execution time Memory
790386 2023-07-22T15:33:05 Z alexander707070 Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 265220 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 400007
using namespace std;

struct event{
    int par;
    long long s;
    int minw;
};

int n,parent[MAXN],to[MAXN],last,comp[MAXN],x;
int win[MAXN],lose[MAXN],k;
vector<int> v[MAXN];
long long curr,dist[MAXN];

pair<int,int> dp[MAXN][20];
bool li[MAXN][20];

pair<int,int> ff(int x,int p){
    if(x==0)return {n,0};
    if(p==0)return {parent[x],win[parent[x]]};

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p].first=ff(ff(x,p-1).first,p-1).first;
    dp[x][p].second=max( ff(x,p-1).second , ff(ff(x,p-1).first,p-1).second );
    
    return dp[x][p];
}

event dp2[MAXN][30];
bool li2[MAXN][30];

event ff2(int x,int p){
    if(p==0)return {to[x],lose[x],win[x]};

    if(li2[x][p])return dp2[x][p];
    li2[x][p]=true;

    dp2[x][p].par=ff2(ff2(x,p-1).par,p-1).par;
    dp2[x][p].s=ff2(x,p-1).s + ff2(ff2(x,p-1).par,p-1).s;
    dp2[x][p].minw=min( ff2(x,p-1).minw , ff2(ff2(x,p-1).par,p-1).minw );
    
    return dp2[x][p];
}

void dfs(int x,long long len){
    len+=win[x]; dist[x]=len;
    for(int i=0;i<v[x].size();i++){
        dfs(v[x][i],len);
    }
}

void init(int N,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
    n=N;
    for(int i=0;i<n;i++){
        parent[i]=w[i];
        v[parent[i]].push_back(i);

        to[i]=l[i];

        win[i]=s[i]; lose[i]=p[i];
    }
    parent[n]=n; to[n]=n;

    dfs(n,0);
}

long long simulate(int x, int z){
    curr=z;

    while(x!=n){
        if(curr<win[x]){
            for(int i=29;i>=0;i--){
                if(curr+ff2(x,i).s<ff2(x,i).minw){
                    curr+=ff2(x,i).s;
                    x=ff2(x,i).par;
                }
            }
            while(curr<win[x]){
                curr+=lose[x]; x=to[x];
            }
        }

        last=x;
        for(int i=19;i>=0;i--){
            if(ff(x,i).first!=n and ff(x,i).second<=curr){
                x=ff(x,i).first;
            }
        }

        curr+=dist[last]-dist[parent[x]];
        x=parent[x];
    }

    return curr;
}

/*
int main(){
    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: In function 'void dfs(int, long long int)':
dungeons.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 10836 KB Output is correct
4 Correct 28 ms 23024 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 30 ms 26360 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10740 KB Output is correct
2 Correct 700 ms 113556 KB Output is correct
3 Correct 764 ms 120228 KB Output is correct
4 Correct 767 ms 120400 KB Output is correct
5 Correct 387 ms 234520 KB Output is correct
6 Correct 900 ms 265220 KB Output is correct
7 Correct 890 ms 127572 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Correct 108 ms 57716 KB Output is correct
3 Correct 143 ms 59788 KB Output is correct
4 Correct 69 ms 24544 KB Output is correct
5 Correct 70 ms 23688 KB Output is correct
6 Correct 138 ms 58500 KB Output is correct
7 Correct 137 ms 56892 KB Output is correct
8 Correct 94 ms 49912 KB Output is correct
9 Correct 83 ms 52764 KB Output is correct
10 Correct 65 ms 24468 KB Output is correct
11 Correct 160 ms 50496 KB Output is correct
12 Correct 304 ms 59592 KB Output is correct
13 Correct 283 ms 58692 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Correct 108 ms 57716 KB Output is correct
3 Correct 143 ms 59788 KB Output is correct
4 Correct 69 ms 24544 KB Output is correct
5 Correct 70 ms 23688 KB Output is correct
6 Correct 138 ms 58500 KB Output is correct
7 Correct 137 ms 56892 KB Output is correct
8 Correct 94 ms 49912 KB Output is correct
9 Correct 83 ms 52764 KB Output is correct
10 Correct 65 ms 24468 KB Output is correct
11 Correct 160 ms 50496 KB Output is correct
12 Correct 304 ms 59592 KB Output is correct
13 Correct 283 ms 58692 KB Output is correct
14 Correct 6 ms 10068 KB Output is correct
15 Correct 580 ms 24168 KB Output is correct
16 Correct 113 ms 58756 KB Output is correct
17 Correct 64 ms 23512 KB Output is correct
18 Correct 70 ms 23612 KB Output is correct
19 Correct 281 ms 59072 KB Output is correct
20 Correct 163 ms 59136 KB Output is correct
21 Correct 128 ms 58888 KB Output is correct
22 Execution timed out 7022 ms 59504 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Correct 108 ms 57716 KB Output is correct
3 Correct 143 ms 59788 KB Output is correct
4 Correct 69 ms 24544 KB Output is correct
5 Correct 70 ms 23688 KB Output is correct
6 Correct 138 ms 58500 KB Output is correct
7 Correct 137 ms 56892 KB Output is correct
8 Correct 94 ms 49912 KB Output is correct
9 Correct 83 ms 52764 KB Output is correct
10 Correct 65 ms 24468 KB Output is correct
11 Correct 160 ms 50496 KB Output is correct
12 Correct 304 ms 59592 KB Output is correct
13 Correct 283 ms 58692 KB Output is correct
14 Correct 6 ms 10068 KB Output is correct
15 Correct 580 ms 24168 KB Output is correct
16 Correct 113 ms 58756 KB Output is correct
17 Correct 64 ms 23512 KB Output is correct
18 Correct 70 ms 23612 KB Output is correct
19 Correct 281 ms 59072 KB Output is correct
20 Correct 163 ms 59136 KB Output is correct
21 Correct 128 ms 58888 KB Output is correct
22 Execution timed out 7022 ms 59504 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10740 KB Output is correct
2 Correct 700 ms 113556 KB Output is correct
3 Correct 764 ms 120228 KB Output is correct
4 Correct 767 ms 120400 KB Output is correct
5 Correct 387 ms 234520 KB Output is correct
6 Correct 900 ms 265220 KB Output is correct
7 Correct 890 ms 127572 KB Output is correct
8 Correct 6 ms 10708 KB Output is correct
9 Correct 108 ms 57716 KB Output is correct
10 Correct 143 ms 59788 KB Output is correct
11 Correct 69 ms 24544 KB Output is correct
12 Correct 70 ms 23688 KB Output is correct
13 Correct 138 ms 58500 KB Output is correct
14 Correct 137 ms 56892 KB Output is correct
15 Correct 94 ms 49912 KB Output is correct
16 Correct 83 ms 52764 KB Output is correct
17 Correct 65 ms 24468 KB Output is correct
18 Correct 160 ms 50496 KB Output is correct
19 Correct 304 ms 59592 KB Output is correct
20 Correct 283 ms 58692 KB Output is correct
21 Correct 6 ms 10068 KB Output is correct
22 Correct 580 ms 24168 KB Output is correct
23 Correct 113 ms 58756 KB Output is correct
24 Correct 64 ms 23512 KB Output is correct
25 Correct 70 ms 23612 KB Output is correct
26 Correct 281 ms 59072 KB Output is correct
27 Correct 163 ms 59136 KB Output is correct
28 Correct 128 ms 58888 KB Output is correct
29 Execution timed out 7022 ms 59504 KB Time limit exceeded
30 Halted 0 ms 0 KB -