oj.uz

Submission #444261

# Submission time Handle Problem Language Result Execution time Memory
444261 2021-07-13T12:55:01 Z urd05 Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 207892 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

int s[400000];
int p[400000];
int w[400000];
int l[400000];
int n;
vector<long long> vec;
typedef pair<long long,long long> P;
int nt[4000001][24];
P table[400001][24];

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
    n=nn;
    for(int i=0;i<n;i++) {
        s[i]=ss[i];
        p[i]=pp[i];
        w[i]=ww[i];
        l[i]=ll[i];
    }
    for(int i=0;i<=n;i++) {
        nt[i][0]=(i==n?n:w[i]);
        table[i][0]=P(-s[i],s[i]);
    }
    for(int j=1;j<24;j++) {
        for(int i=0;i<=n;i++) {
            nt[i][j]=nt[nt[i][j-1]][j-1];
            table[i][j]=P(min(table[i][j-1].first,table[i][j-1].second+table[nt[i][j-1]][j-1].first),table[i][j-1].second+table[nt[i][j-1]][j-1].second);
        }
    }
	return;
}

int getind(int val) {
    return upper_bound(vec.begin(),vec.end(),val)-vec.begin();
}

long long simulate(int x, int zz) {
    long long z=zz;
    while (x!=n) {
        for(int i=23;i>=0;i--) {
            if (nt[x][i]!=n&&z>=-table[x][i].first) {
                z+=table[x][i].second;
                x=nt[x][i];
            }
        }
        if (z>=s[x]) {
            z+=s[x];
            x=w[x];
        }
        else {
            z+=p[x];
            x=l[x];
        }
    }
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 58 ms 26052 KB Output is correct
5 Correct 4 ms 1356 KB Output is correct
6 Correct 57 ms 26160 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 552 ms 207752 KB Output is correct
3 Correct 530 ms 207812 KB Output is correct
4 Correct 547 ms 207812 KB Output is correct
5 Correct 526 ms 207892 KB Output is correct
6 Correct 577 ms 207760 KB Output is correct
7 Correct 522 ms 207856 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 91 ms 27076 KB Output is correct
3 Correct 110 ms 26952 KB Output is correct
4 Correct 91 ms 26956 KB Output is correct
5 Correct 98 ms 26840 KB Output is correct
6 Execution timed out 7031 ms 26848 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 91 ms 27076 KB Output is correct
3 Correct 110 ms 26952 KB Output is correct
4 Correct 91 ms 26956 KB Output is correct
5 Correct 98 ms 26840 KB Output is correct
6 Execution timed out 7031 ms 26848 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 91 ms 27076 KB Output is correct
3 Correct 110 ms 26952 KB Output is correct
4 Correct 91 ms 26956 KB Output is correct
5 Correct 98 ms 26840 KB Output is correct
6 Execution timed out 7031 ms 26848 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 552 ms 207752 KB Output is correct
3 Correct 530 ms 207812 KB Output is correct
4 Correct 547 ms 207812 KB Output is correct
5 Correct 526 ms 207892 KB Output is correct
6 Correct 577 ms 207760 KB Output is correct
7 Correct 522 ms 207856 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 91 ms 27076 KB Output is correct
10 Correct 110 ms 26952 KB Output is correct
11 Correct 91 ms 26956 KB Output is correct
12 Correct 98 ms 26840 KB Output is correct
13 Execution timed out 7031 ms 26848 KB Time limit exceeded
14 Halted 0 ms 0 KB -