oj.uz

Submission #856458

# Submission time Handle Problem Language Result Execution time Memory
856458 2023-10-03T14:50:07 Z andrei_boaca Dungeons Game (IOI21_dungeons) C++17
62 / 100
 7000 ms 1084076 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,s[400005],p[400005],w[400005],l[400005],smax;
bool sub2=0,sub4=0;
vector<ll> mys;
struct date
{
    ll maxim,poz,suma;
} dp[400005][22],whereL[400005],whereR[400005];
ll getver(ll x)
{
    for(int i=0;i<mys.size();i++)
        if(mys[i]>x)
            return i;
    return mys.size();
}
pll ver[7][400005][22]; // {suma,poz}
date tour(ll poz,ll val)
{
    if(dp[poz][20].maxim<=val)
        return {0,n,dp[poz][20].suma};
    ll suma=0;
    for(ll j=20;j>=0;j--)
        if(dp[poz][j].maxim<=val)
        {
            suma+=dp[poz][j].suma;
            poz=w[dp[poz][j].poz];
        }
    return {0,poz,suma};
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    n=N;
    sub2=1;
    for(int i=0;i<n;i++)
    {
        s[i]=S[i];
        mys.push_back(s[i]);
        smax=max(smax,s[i]);
        p[i]=P[i];
        if(s[i]!=p[i])
            sub2=0;
        w[i]=W[i];
        l[i]=L[i];
    }
    sort(mys.begin(),mys.end());
    mys.erase(unique(mys.begin(),mys.end()),mys.end());
    w[n]=n;
    if(mys.size()<=5)
    {
        sub4=1;
        for(int v=0;v<=mys.size();v++)
        {
            ll lim=1e9;
            if(v<mys.size())
                lim=mys[v];
            for(int i=0;i<=20;i++)
                ver[v][n][i]={0,n};
            for(int i=0;i<n;i++)
            {
                if(s[i]>=lim)
                {
                    ver[v][i][0].first=p[i];
                    ver[v][i][0].second=l[i];
                }
                else
                {
                    ver[v][i][0].first=s[i];
                    ver[v][i][0].second=w[i];
                }
            }
            for(int j=1;j<=20;j++)
            {
                for(int i=0;i<n;i++)
                {
                    int poz=ver[v][i][j-1].second;
                    ver[v][i][j].second=ver[v][poz][j-1].second;
                    ver[v][i][j].first=ver[v][i][j-1].first+ver[v][poz][j-1].first;
                }
            }
        }
    }
    if(sub2)
    {
        for(int j=0;j<=20;j++)
            dp[n][j]={0,n,0};
        for(int i=n-1;i>=0;i--)
        {
            dp[i][0]={s[i],i,s[i]};
            for(int j=1;j<=20;j++)
            {
                ll p=w[dp[i][j-1].poz];
                ll poz=dp[p][j-1].poz;
                dp[i][j].poz=poz;
                dp[i][j].maxim=max(dp[i][j-1].maxim,dp[p][j-1].maxim);
                dp[i][j].suma=dp[i][j-1].suma+dp[p][j-1].suma;
            }
        }
        for(int i=0;i<n;i++)
        {
            whereL[i]=tour(l[i],s[i]);
            whereR[i]=tour(w[i],s[i]);
        }
    }
}

long long simulate(int x, int z)
{
    ll rez=z;
    if(x==n)
        return rez;
    if(sub4)
    {
        while(x!=n)
        {
            ll v=getver(rez);
            for(ll j=20;j>=0;j--)
                if(getver(ver[v][x][j].first+rez)==v)
                {
                    rez+=ver[v][x][j].first;
                    x=ver[v][x][j].second;
                }
            if(x==n)
                break;
            if(rez>=s[x])
            {
                rez+=s[x];
                x=w[x];
            }
            else
            {
                rez+=p[x];
                x=l[x];
            }
        }
        return rez;
    }
    if(sub2)
    {
        while(x!=n)
        {
            if(rez>=s[x])
            {
                rez+=s[x];
                if(rez>=smax)
                {
                    rez+=dp[w[x]][20].suma;
                    return rez;
                }
                rez+=whereR[x].suma;
                x=whereR[x].poz;
            }
            else
            {
                rez+=s[x];
                if(rez>=smax)
                {
                    rez+=dp[l[x]][20].suma;
                    return rez;
                }
                rez+=whereL[x].suma;
                x=whereL[x].poz;
            }
        }
        return rez;
    }
    while(x!=n)
    {
        if(rez>=s[x])
        {
            rez+=s[x];
            x=w[x];
        }
        else
        {
            rez+=p[x];
            x=l[x];
        }
    }
    return rez;
}

Compilation message

dungeons.cpp: In function 'll getver(ll)':
dungeons.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<mys.size();i++)
      |                 ~^~~~~~~~~~~
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int v=0;v<=mys.size();v++)
      |                     ~^~~~~~~~~~~~
dungeons.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             if(v<mys.size())
      |                ~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8624 KB Output is correct
4 Correct 19 ms 10836 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 18 ms 10712 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 507 ms 256960 KB Output is correct
3 Correct 564 ms 256892 KB Output is correct
4 Correct 1030 ms 944908 KB Output is correct
5 Correct 848 ms 1084076 KB Output is correct
6 Correct 511 ms 256808 KB Output is correct
7 Correct 437 ms 257532 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 47 ms 48592 KB Output is correct
3 Correct 50 ms 48588 KB Output is correct
4 Correct 43 ms 49612 KB Output is correct
5 Correct 43 ms 49620 KB Output is correct
6 Correct 54 ms 49500 KB Output is correct
7 Correct 69 ms 49640 KB Output is correct
8 Correct 45 ms 49600 KB Output is correct
9 Correct 45 ms 49472 KB Output is correct
10 Correct 43 ms 49232 KB Output is correct
11 Correct 43 ms 49620 KB Output is correct
12 Correct 326 ms 49608 KB Output is correct
13 Correct 333 ms 49620 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 47 ms 48592 KB Output is correct
3 Correct 50 ms 48588 KB Output is correct
4 Correct 43 ms 49612 KB Output is correct
5 Correct 43 ms 49620 KB Output is correct
6 Correct 54 ms 49500 KB Output is correct
7 Correct 69 ms 49640 KB Output is correct
8 Correct 45 ms 49600 KB Output is correct
9 Correct 45 ms 49472 KB Output is correct
10 Correct 43 ms 49232 KB Output is correct
11 Correct 43 ms 49620 KB Output is correct
12 Correct 326 ms 49608 KB Output is correct
13 Correct 333 ms 49620 KB Output is correct
14 Correct 3 ms 19036 KB Output is correct
15 Correct 66 ms 86724 KB Output is correct
16 Correct 71 ms 105160 KB Output is correct
17 Correct 71 ms 125384 KB Output is correct
18 Correct 84 ms 125456 KB Output is correct
19 Correct 100 ms 125536 KB Output is correct
20 Correct 78 ms 86472 KB Output is correct
21 Correct 93 ms 105052 KB Output is correct
22 Correct 58 ms 68044 KB Output is correct
23 Correct 80 ms 105156 KB Output is correct
24 Correct 126 ms 86472 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 47 ms 48592 KB Output is correct
3 Correct 50 ms 48588 KB Output is correct
4 Correct 43 ms 49612 KB Output is correct
5 Correct 43 ms 49620 KB Output is correct
6 Correct 54 ms 49500 KB Output is correct
7 Correct 69 ms 49640 KB Output is correct
8 Correct 45 ms 49600 KB Output is correct
9 Correct 45 ms 49472 KB Output is correct
10 Correct 43 ms 49232 KB Output is correct
11 Correct 43 ms 49620 KB Output is correct
12 Correct 326 ms 49608 KB Output is correct
13 Correct 333 ms 49620 KB Output is correct
14 Correct 3 ms 19036 KB Output is correct
15 Correct 66 ms 86724 KB Output is correct
16 Correct 71 ms 105160 KB Output is correct
17 Correct 71 ms 125384 KB Output is correct
18 Correct 84 ms 125456 KB Output is correct
19 Correct 100 ms 125536 KB Output is correct
20 Correct 78 ms 86472 KB Output is correct
21 Correct 93 ms 105052 KB Output is correct
22 Correct 58 ms 68044 KB Output is correct
23 Correct 80 ms 105156 KB Output is correct
24 Correct 126 ms 86472 KB Output is correct
25 Correct 20 ms 11856 KB Output is correct
26 Correct 35 ms 12748 KB Output is correct
27 Correct 35 ms 12500 KB Output is correct
28 Correct 307 ms 12504 KB Output is correct
29 Correct 44 ms 12760 KB Output is correct
30 Execution timed out 7015 ms 12492 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 507 ms 256960 KB Output is correct
3 Correct 564 ms 256892 KB Output is correct
4 Correct 1030 ms 944908 KB Output is correct
5 Correct 848 ms 1084076 KB Output is correct
6 Correct 511 ms 256808 KB Output is correct
7 Correct 437 ms 257532 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 47 ms 48592 KB Output is correct
10 Correct 50 ms 48588 KB Output is correct
11 Correct 43 ms 49612 KB Output is correct
12 Correct 43 ms 49620 KB Output is correct
13 Correct 54 ms 49500 KB Output is correct
14 Correct 69 ms 49640 KB Output is correct
15 Correct 45 ms 49600 KB Output is correct
16 Correct 45 ms 49472 KB Output is correct
17 Correct 43 ms 49232 KB Output is correct
18 Correct 43 ms 49620 KB Output is correct
19 Correct 326 ms 49608 KB Output is correct
20 Correct 333 ms 49620 KB Output is correct
21 Correct 3 ms 19036 KB Output is correct
22 Correct 66 ms 86724 KB Output is correct
23 Correct 71 ms 105160 KB Output is correct
24 Correct 71 ms 125384 KB Output is correct
25 Correct 84 ms 125456 KB Output is correct
26 Correct 100 ms 125536 KB Output is correct
27 Correct 78 ms 86472 KB Output is correct
28 Correct 93 ms 105052 KB Output is correct
29 Correct 58 ms 68044 KB Output is correct
30 Correct 80 ms 105156 KB Output is correct
31 Correct 126 ms 86472 KB Output is correct
32 Correct 20 ms 11856 KB Output is correct
33 Correct 35 ms 12748 KB Output is correct
34 Correct 35 ms 12500 KB Output is correct
35 Correct 307 ms 12504 KB Output is correct
36 Correct 44 ms 12760 KB Output is correct
37 Execution timed out 7015 ms 12492 KB Time limit exceeded
38 Halted 0 ms 0 KB -