oj.uz

Submission #598692

# Submission time Handle Problem Language Result Execution time Memory
598692 2022-07-18T17:51:55 Z MKopchev Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5181 ms 235056 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=4e5+42,C=3000,SZ=24;

int mem_n;

vector<int> opponent_power,lose_gain,win_move,lose_move;

long long gain_only_wins[nmax];
long long lowest_only_wins[nmax];

long long gain_large_win[nmax];
int win_move_large[nmax];

long long gain_large_lose[nmax];
int lose_move_large[nmax];

long long highest_only_losses[SZ][nmax];
long long gain_only_losses[SZ][nmax];
int move_only_losses[SZ][nmax];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
	mem_n=n;

	opponent_power=s;

	lose_gain=p;

	win_move=w;

	lose_move=l;

	for(int i=n-1;i>=0;i--)
    {
        gain_only_wins[i]=opponent_power[i]+gain_only_wins[win_move[i]];

        lowest_only_wins[i]=max(1LL*opponent_power[i],lowest_only_wins[win_move[i]]-opponent_power[i]);
    }

    for(int i=n-1;i>=0;i--)
    {
        gain_large_win[i]=opponent_power[i];
        win_move_large[i]=win_move[i];

        if(win_move[i]!=n&&opponent_power[win_move[i]]<C)
        {
            win_move_large[i]=win_move_large[win_move[i]];
            gain_large_win[i]+=gain_large_win[win_move[i]];
        }
    }

    for(int i=n-1;i>=0;i--)
    {
        gain_large_lose[i]=lose_gain[i];
        lose_move_large[i]=lose_move[i];

        if(lose_move[i]!=n&&opponent_power[lose_move[i]]<C)
        {
            lose_move_large[i]=win_move_large[lose_move[i]];
            gain_large_lose[i]+=gain_large_win[lose_move[i]];
        }
    }

    for(int i=0;i<n;i++)
    {
        highest_only_losses[0][i]=opponent_power[i]-1;
        gain_only_losses[0][i]=gain_large_lose[i];
        move_only_losses[0][i]=lose_move_large[i];
    }

    for(int step=1;step<SZ;step++)
        for(int i=0;i<n;i++)
        {
            highest_only_losses[step][i]=min(highest_only_losses[step-1][i],highest_only_losses[step-1][move_only_losses[step-1][i]]-gain_only_losses[step-1][i]);

            gain_only_losses[step][i]=gain_only_losses[step-1][i]+gain_only_losses[step-1][move_only_losses[step-1][i]];

            move_only_losses[step][i]=move_only_losses[step-1][move_only_losses[step-1][i]];
        }

    /*
    for(int i=0;i<n;i++)
        cout<<i<<" -> "<<win_move_large[i]<<" "<<gain_large_win[i]<<" "<<lose_move_large[i]<<" "<<gain_large_lose[i]<<endl;
    */

}

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

    while(z<lowest_only_wins[x]&&z<C)
    {
        if(opponent_power[x]<=z)
        {
            z+=opponent_power[x];
            x=win_move[x];
        }
        else
        {
            z+=lose_gain[x];
            x=lose_move[x];
        }
    }

    if(z>=lowest_only_wins[x])return z+gain_only_wins[x];

    while(z<lowest_only_wins[x])
    {
        if(opponent_power[x]<=z)
        {
            z+=gain_large_win[x];
            x=win_move_large[x];
        }
        else
        {
            /*
            z+=gain_large_lose[x];
            x=lose_move_large[x];
            */

            for(int j=SZ-1;j>=0;j--)
                if(z<=highest_only_losses[j][x])
                {
                    //cout<<"jump "<<z<<" "<<j<<" "<<x<<" "<<gain_only_losses[j][x]<<" "<<move_only_losses[j][x]<<endl;

                    z+=gain_only_losses[j][x];
                    x=move_only_losses[j][x];
                }
        }
    }

    z+=gain_only_wins[x];

    return z;
}

/*
static int n, q;
static std::vector<int> s, p, z;
static std::vector<int> w, l, x;
static std::vector<long long> answer;

int main() {
	assert(scanf("%d %d", &n, &q) == 2);
	s.resize(n);
	p.resize(n);
	w.resize(n);
	l.resize(n);
    x.resize(q);
    z.resize(q);
    answer.resize(q);

	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &s[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &p[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &w[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &l[i]) == 1);
	}


    init(n, s, p, w, l);

    for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &z[i]) == 2);
		answer[i] = simulate(x[i], z[i]);
    }
    fclose(stdin);

    for (int i = 0; i < q; i++) {
        printf("%lld\n", answer[i]);
    }
    fclose(stdout);
    return 0;
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 29 ms 28620 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 30 ms 28536 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 235 ms 223320 KB Output is correct
3 Correct 242 ms 223416 KB Output is correct
4 Correct 242 ms 223416 KB Output is correct
5 Correct 259 ms 223392 KB Output is correct
6 Correct 336 ms 223416 KB Output is correct
7 Correct 368 ms 223308 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 55 ms 29400 KB Output is correct
3 Correct 56 ms 29344 KB Output is correct
4 Correct 45 ms 29408 KB Output is correct
5 Correct 43 ms 29412 KB Output is correct
6 Correct 95 ms 29320 KB Output is correct
7 Correct 297 ms 29436 KB Output is correct
8 Correct 42 ms 29360 KB Output is correct
9 Correct 43 ms 29404 KB Output is correct
10 Correct 44 ms 29408 KB Output is correct
11 Correct 1690 ms 29404 KB Output is correct
12 Correct 1685 ms 29388 KB Output is correct
13 Correct 470 ms 29396 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 55 ms 29400 KB Output is correct
3 Correct 56 ms 29344 KB Output is correct
4 Correct 45 ms 29408 KB Output is correct
5 Correct 43 ms 29412 KB Output is correct
6 Correct 95 ms 29320 KB Output is correct
7 Correct 297 ms 29436 KB Output is correct
8 Correct 42 ms 29360 KB Output is correct
9 Correct 43 ms 29404 KB Output is correct
10 Correct 44 ms 29408 KB Output is correct
11 Correct 1690 ms 29404 KB Output is correct
12 Correct 1685 ms 29388 KB Output is correct
13 Correct 470 ms 29396 KB Output is correct
14 Correct 1 ms 1364 KB Output is correct
15 Correct 67 ms 29400 KB Output is correct
16 Correct 55 ms 29336 KB Output is correct
17 Correct 45 ms 29412 KB Output is correct
18 Correct 46 ms 29436 KB Output is correct
19 Correct 103 ms 29404 KB Output is correct
20 Correct 88 ms 29404 KB Output is correct
21 Correct 46 ms 29408 KB Output is correct
22 Correct 521 ms 29404 KB Output is correct
23 Correct 1894 ms 29456 KB Output is correct
24 Correct 439 ms 29396 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 55 ms 29400 KB Output is correct
3 Correct 56 ms 29344 KB Output is correct
4 Correct 45 ms 29408 KB Output is correct
5 Correct 43 ms 29412 KB Output is correct
6 Correct 95 ms 29320 KB Output is correct
7 Correct 297 ms 29436 KB Output is correct
8 Correct 42 ms 29360 KB Output is correct
9 Correct 43 ms 29404 KB Output is correct
10 Correct 44 ms 29408 KB Output is correct
11 Correct 1690 ms 29404 KB Output is correct
12 Correct 1685 ms 29388 KB Output is correct
13 Correct 470 ms 29396 KB Output is correct
14 Correct 1 ms 1364 KB Output is correct
15 Correct 67 ms 29400 KB Output is correct
16 Correct 55 ms 29336 KB Output is correct
17 Correct 45 ms 29412 KB Output is correct
18 Correct 46 ms 29436 KB Output is correct
19 Correct 103 ms 29404 KB Output is correct
20 Correct 88 ms 29404 KB Output is correct
21 Correct 46 ms 29408 KB Output is correct
22 Correct 521 ms 29404 KB Output is correct
23 Correct 1894 ms 29456 KB Output is correct
24 Correct 439 ms 29396 KB Output is correct
25 Correct 31 ms 28620 KB Output is correct
26 Correct 64 ms 29524 KB Output is correct
27 Correct 51 ms 29328 KB Output is correct
28 Correct 51 ms 29444 KB Output is correct
29 Correct 69 ms 29400 KB Output is correct
30 Correct 81 ms 29332 KB Output is correct
31 Correct 83 ms 29456 KB Output is correct
32 Correct 275 ms 29404 KB Output is correct
33 Correct 198 ms 30632 KB Output is correct
34 Correct 479 ms 30540 KB Output is correct
35 Correct 1522 ms 30540 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 235 ms 223320 KB Output is correct
3 Correct 242 ms 223416 KB Output is correct
4 Correct 242 ms 223416 KB Output is correct
5 Correct 259 ms 223392 KB Output is correct
6 Correct 336 ms 223416 KB Output is correct
7 Correct 368 ms 223308 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 55 ms 29400 KB Output is correct
10 Correct 56 ms 29344 KB Output is correct
11 Correct 45 ms 29408 KB Output is correct
12 Correct 43 ms 29412 KB Output is correct
13 Correct 95 ms 29320 KB Output is correct
14 Correct 297 ms 29436 KB Output is correct
15 Correct 42 ms 29360 KB Output is correct
16 Correct 43 ms 29404 KB Output is correct
17 Correct 44 ms 29408 KB Output is correct
18 Correct 1690 ms 29404 KB Output is correct
19 Correct 1685 ms 29388 KB Output is correct
20 Correct 470 ms 29396 KB Output is correct
21 Correct 1 ms 1364 KB Output is correct
22 Correct 67 ms 29400 KB Output is correct
23 Correct 55 ms 29336 KB Output is correct
24 Correct 45 ms 29412 KB Output is correct
25 Correct 46 ms 29436 KB Output is correct
26 Correct 103 ms 29404 KB Output is correct
27 Correct 88 ms 29404 KB Output is correct
28 Correct 46 ms 29408 KB Output is correct
29 Correct 521 ms 29404 KB Output is correct
30 Correct 1894 ms 29456 KB Output is correct
31 Correct 439 ms 29396 KB Output is correct
32 Correct 31 ms 28620 KB Output is correct
33 Correct 64 ms 29524 KB Output is correct
34 Correct 51 ms 29328 KB Output is correct
35 Correct 51 ms 29444 KB Output is correct
36 Correct 69 ms 29400 KB Output is correct
37 Correct 81 ms 29332 KB Output is correct
38 Correct 83 ms 29456 KB Output is correct
39 Correct 275 ms 29404 KB Output is correct
40 Correct 198 ms 30632 KB Output is correct
41 Correct 479 ms 30540 KB Output is correct
42 Correct 1522 ms 30540 KB Output is correct
43 Correct 1 ms 852 KB Output is correct
44 Correct 1 ms 1492 KB Output is correct
45 Correct 305 ms 235048 KB Output is correct
46 Correct 246 ms 230388 KB Output is correct
47 Correct 244 ms 230800 KB Output is correct
48 Correct 306 ms 232908 KB Output is correct
49 Correct 306 ms 235056 KB Output is correct
50 Correct 266 ms 232520 KB Output is correct
51 Correct 265 ms 233004 KB Output is correct
52 Correct 267 ms 230604 KB Output is correct
53 Correct 903 ms 231452 KB Output is correct
54 Correct 706 ms 232612 KB Output is correct
55 Correct 1113 ms 231564 KB Output is correct
56 Correct 5181 ms 232216 KB Output is correct
57 Correct 3548 ms 232296 KB Output is correct
58 Correct 2392 ms 232264 KB Output is correct
59 Correct 2039 ms 232452 KB Output is correct
60 Correct 2203 ms 231748 KB Output is correct
61 Correct 2221 ms 231720 KB Output is correct