oj.uz

Submission #790384

# Submission time Handle Problem Language Result Execution time Memory
790384 2023-07-22T15:31:04 Z alexander707070 Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 276272 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],pref,minloops,tocomp[MAXN];
int pos[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);
    }
}

bool in[MAXN],dali,incyc[MAXN];
vector<int> cycle[MAXN];
long long sum[MAXN];
int u[MAXN],tim,minw[MAXN];

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);

    for(int i=0;i<n;i++){
        if(u[i]!=0)continue;
        tim++; x=i;

        while(true){
            u[x]=tim; x=to[x];
            if(u[x]>0 and u[x]!=tim)break;

            if(u[x]==tim){
                last=x; k++; comp[x]=k; sum[k]=lose[x];
                cycle[k].push_back({x}); incyc[x]=true; x=to[x];
                while(x!=last){
                    cycle[k].push_back(x); comp[x]=k; 
                    sum[k]+=lose[x]; u[x]=tim; incyc[x]=true;
                    x=to[x];
                }
                break;
            }
        }
    }

    for(int i=0;i<=k;i++){
        minw[i]=100000000;
        for(int f=0;f<cycle[i].size();f++){
            pos[cycle[i][f]]=f;
            minw[i]=min(minw[i],win[cycle[i][f]]);
        }
    }
}

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19156 KB Output is correct
2 Correct 13 ms 19216 KB Output is correct
3 Correct 11 ms 20180 KB Output is correct
4 Correct 34 ms 32940 KB Output is correct
5 Correct 11 ms 20692 KB Output is correct
6 Correct 34 ms 36260 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20184 KB Output is correct
2 Correct 688 ms 124476 KB Output is correct
3 Correct 759 ms 131264 KB Output is correct
4 Correct 759 ms 131492 KB Output is correct
5 Correct 391 ms 245220 KB Output is correct
6 Correct 906 ms 276272 KB Output is correct
7 Correct 824 ms 138484 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20052 KB Output is correct
2 Correct 124 ms 67720 KB Output is correct
3 Correct 156 ms 69416 KB Output is correct
4 Correct 76 ms 34096 KB Output is correct
5 Correct 69 ms 33412 KB Output is correct
6 Correct 141 ms 68476 KB Output is correct
7 Correct 142 ms 66832 KB Output is correct
8 Correct 99 ms 59808 KB Output is correct
9 Correct 101 ms 62688 KB Output is correct
10 Correct 71 ms 34096 KB Output is correct
11 Correct 170 ms 60140 KB Output is correct
12 Correct 309 ms 69912 KB Output is correct
13 Correct 290 ms 68980 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20052 KB Output is correct
2 Correct 124 ms 67720 KB Output is correct
3 Correct 156 ms 69416 KB Output is correct
4 Correct 76 ms 34096 KB Output is correct
5 Correct 69 ms 33412 KB Output is correct
6 Correct 141 ms 68476 KB Output is correct
7 Correct 142 ms 66832 KB Output is correct
8 Correct 99 ms 59808 KB Output is correct
9 Correct 101 ms 62688 KB Output is correct
10 Correct 71 ms 34096 KB Output is correct
11 Correct 170 ms 60140 KB Output is correct
12 Correct 309 ms 69912 KB Output is correct
13 Correct 290 ms 68980 KB Output is correct
14 Correct 11 ms 19540 KB Output is correct
15 Correct 593 ms 34176 KB Output is correct
16 Correct 127 ms 68796 KB Output is correct
17 Correct 69 ms 34700 KB Output is correct
18 Correct 79 ms 34880 KB Output is correct
19 Correct 305 ms 70780 KB Output is correct
20 Correct 174 ms 70100 KB Output is correct
21 Correct 143 ms 69968 KB Output is correct
22 Execution timed out 7020 ms 70228 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20052 KB Output is correct
2 Correct 124 ms 67720 KB Output is correct
3 Correct 156 ms 69416 KB Output is correct
4 Correct 76 ms 34096 KB Output is correct
5 Correct 69 ms 33412 KB Output is correct
6 Correct 141 ms 68476 KB Output is correct
7 Correct 142 ms 66832 KB Output is correct
8 Correct 99 ms 59808 KB Output is correct
9 Correct 101 ms 62688 KB Output is correct
10 Correct 71 ms 34096 KB Output is correct
11 Correct 170 ms 60140 KB Output is correct
12 Correct 309 ms 69912 KB Output is correct
13 Correct 290 ms 68980 KB Output is correct
14 Correct 11 ms 19540 KB Output is correct
15 Correct 593 ms 34176 KB Output is correct
16 Correct 127 ms 68796 KB Output is correct
17 Correct 69 ms 34700 KB Output is correct
18 Correct 79 ms 34880 KB Output is correct
19 Correct 305 ms 70780 KB Output is correct
20 Correct 174 ms 70100 KB Output is correct
21 Correct 143 ms 69968 KB Output is correct
22 Execution timed out 7020 ms 70228 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20184 KB Output is correct
2 Correct 688 ms 124476 KB Output is correct
3 Correct 759 ms 131264 KB Output is correct
4 Correct 759 ms 131492 KB Output is correct
5 Correct 391 ms 245220 KB Output is correct
6 Correct 906 ms 276272 KB Output is correct
7 Correct 824 ms 138484 KB Output is correct
8 Correct 11 ms 20052 KB Output is correct
9 Correct 124 ms 67720 KB Output is correct
10 Correct 156 ms 69416 KB Output is correct
11 Correct 76 ms 34096 KB Output is correct
12 Correct 69 ms 33412 KB Output is correct
13 Correct 141 ms 68476 KB Output is correct
14 Correct 142 ms 66832 KB Output is correct
15 Correct 99 ms 59808 KB Output is correct
16 Correct 101 ms 62688 KB Output is correct
17 Correct 71 ms 34096 KB Output is correct
18 Correct 170 ms 60140 KB Output is correct
19 Correct 309 ms 69912 KB Output is correct
20 Correct 290 ms 68980 KB Output is correct
21 Correct 11 ms 19540 KB Output is correct
22 Correct 593 ms 34176 KB Output is correct
23 Correct 127 ms 68796 KB Output is correct
24 Correct 69 ms 34700 KB Output is correct
25 Correct 79 ms 34880 KB Output is correct
26 Correct 305 ms 70780 KB Output is correct
27 Correct 174 ms 70100 KB Output is correct
28 Correct 143 ms 69968 KB Output is correct
29 Execution timed out 7020 ms 70228 KB Time limit exceeded
30 Halted 0 ms 0 KB -