oj.uz

Submission #442849

# Submission time Handle Problem Language Result Execution time Memory
442849 2021-07-09T09:06:08 Z baluteshih Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 172884 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

struct node {
    int to, lower;
    ll sum;
    node operator+(const node &a) const {
        node rt;
        rt.to = a.to;
        rt.sum = sum + a.sum;
        if (lower + sum < a.lower)
            rt.lower = a.lower - sum;
        else
            rt.lower = lower;
        return rt;
    }
};

int N, lg = __lg(10000000);
vector<int> S, P, W, L;
vector<node> dp[30];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n, S = s, P = p, W = w, L = l;
    dp[0].resize(N + 1);
    dp[0][N] = node{N, 0, 0};
    for (int i = 0; i < N; ++i)
       dp[0][i] = node{W[i], S[i], S[i]};
    for (int i = 1; i <= lg; ++i) {
        dp[i].resize(N + 1);
        for (int j = 0; j <= N; ++j)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][dp[i - 1][j].to];
    }
}

long long simulate(int x, int z) {
    ll nw = z;
    while (dp[lg][x].lower > nw) {
        for (int i = lg; i >= 0; --i)
            if (dp[i][x].lower <= nw) {
                nw += dp[i][x].sum;
                x = dp[i][x].to;
            }
        nw += P[x];
        x = L[x];
    }
    return nw + dp[lg][x].sum;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 38 ms 21964 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct
6 Correct 41 ms 21924 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 351 ms 172884 KB Output is correct
3 Correct 322 ms 170916 KB Output is correct
4 Correct 312 ms 170676 KB Output is correct
5 Correct 377 ms 170612 KB Output is correct
6 Correct 380 ms 170476 KB Output is correct
7 Correct 354 ms 170516 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 67 ms 22780 KB Output is correct
3 Correct 100 ms 22864 KB Output is correct
4 Correct 57 ms 22844 KB Output is correct
5 Correct 53 ms 22780 KB Output is correct
6 Execution timed out 7075 ms 22776 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 716 KB Output is correct
2 Correct 67 ms 22780 KB Output is correct
3 Correct 100 ms 22864 KB Output is correct
4 Correct 57 ms 22844 KB Output is correct
5 Correct 53 ms 22780 KB Output is correct
6 Execution timed out 7075 ms 22776 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 716 KB Output is correct
2 Correct 67 ms 22780 KB Output is correct
3 Correct 100 ms 22864 KB Output is correct
4 Correct 57 ms 22844 KB Output is correct
5 Correct 53 ms 22780 KB Output is correct
6 Execution timed out 7075 ms 22776 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 716 KB Output is correct
2 Correct 351 ms 172884 KB Output is correct
3 Correct 322 ms 170916 KB Output is correct
4 Correct 312 ms 170676 KB Output is correct
5 Correct 377 ms 170612 KB Output is correct
6 Correct 380 ms 170476 KB Output is correct
7 Correct 354 ms 170516 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 67 ms 22780 KB Output is correct
10 Correct 100 ms 22864 KB Output is correct
11 Correct 57 ms 22844 KB Output is correct
12 Correct 53 ms 22780 KB Output is correct
13 Execution timed out 7075 ms 22776 KB Time limit exceeded
14 Halted 0 ms 0 KB -