oj.uz

답안 #755047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
755047 2023-06-09T10:41:37 Z Rafi22 던전 (IOI21_dungeons) C++17
100 / 100
 3475 ms 1985500 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=400007,K=24;

int g[13][K][N];
int mx[13][K][N];
ll sum[13][K][N];
vector<int>S,P,W,L;
int n;

void init(int nn,vector<int>s,vector<int>p,vector<int>w,vector<int>l)
{
    n=nn;
    s.pb(0);
    p.pb(0);
    w.pb(n);
    l.pb(n);
    S=s,P=p,W=w;L=l;
    for(int j=0;j<13;j++)
    {
        for(int i=0;i<=n;i++)
        {
            if(s[i]<(1<<(2*j)))
            {
                g[j][0][i]=w[i];
                sum[j][0][i]=s[i];
                mx[j][0][i]=-inf;
            }
            else
            {
                g[j][0][i]=l[i];
                sum[j][0][i]=p[i];
                mx[j][0][i]=-s[i];
            }
        }
        for(int l=1;l<K;l++)
        {
            for(int i=0;i<=n;i++)
            {
                int x=g[j][l-1][i];
                g[j][l][i]=g[j][l-1][x];
                sum[j][l][i]=sum[j][l-1][i]+sum[j][l-1][x];
                mx[j][l][i]=mx[j][l-1][i];
                if(mx[j][l-1][x]!=-inf) mx[j][l][i]=max(mx[j][l][i],(int)min((ll)inf,sum[j][l-1][i]+mx[j][l-1][x]));
            }
        }
    }
}
int cnt=0;
ll simulate(int x,int z)
{
    ll a=z;
    int j=0;
    while(x!=n)
    {
        while(j<12&&a>=(1LL<<(2*j+2))) j++;
        cnt++;
        for(int l=K-1;l>=0;l--)
        {
            if(g[j][l][x]==n||(mx[j][l][x]!=-inf&&a+mx[j][l][x]>=0)) continue;
            a+=sum[j][l][x];
            x=g[j][l][x];
        }
        if(a>=S[x])
        {
            a+=S[x];
            x=W[x];
        }
        else
        {
            a+=P[x];
            x=L[x];
        }
        while(j<12&&a>=(1LL<<(2*j+2))) j++;
    }
    return a;
}

/*int main()
{
  //  freopen("inn.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
    cout<<simulate(0,1)<<endl;
    cout<<simulate(2,3)<<endl;
  /*  int n,q;
    cin>>n>>q;
    vector<int>sa(n),pa(n),wa(n),la(n);
    for(int i=0;i<n;i++) cin>>sa[i];
    for(int i=0;i<n;i++) cin>>pa[i];
    for(int i=0;i<n;i++) cin>>wa[i];
    for(int i=0;i<n;i++) cin>>la[i];
    init(n,sa,pa,wa,la);
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        simulate(a,b);
    }

    return 0;
}*/

Compilation message

dungeons.cpp:101:3: warning: "/*" within comment [-Wcomment]
  101 |   /*  int n,q;
      |

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7124 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 9 ms 17052 KB Output is correct
4 Correct 143 ms 253516 KB Output is correct
5 Correct 10 ms 17056 KB Output is correct
6 Correct 150 ms 253436 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 1431 ms 1973704 KB Output is correct
3 Correct 1246 ms 1980556 KB Output is correct
4 Correct 1320 ms 1982156 KB Output is correct
5 Correct 1406 ms 1982120 KB Output is correct
6 Correct 1332 ms 1980644 KB Output is correct
7 Correct 1343 ms 1978740 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 294 ms 254280 KB Output is correct
3 Correct 258 ms 254208 KB Output is correct
4 Correct 196 ms 254312 KB Output is correct
5 Correct 186 ms 254268 KB Output is correct
6 Correct 290 ms 254268 KB Output is correct
7 Correct 300 ms 254288 KB Output is correct
8 Correct 213 ms 254332 KB Output is correct
9 Correct 253 ms 254364 KB Output is correct
10 Correct 201 ms 254204 KB Output is correct
11 Correct 235 ms 254264 KB Output is correct
12 Correct 330 ms 254328 KB Output is correct
13 Correct 249 ms 254300 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 294 ms 254280 KB Output is correct
3 Correct 258 ms 254208 KB Output is correct
4 Correct 196 ms 254312 KB Output is correct
5 Correct 186 ms 254268 KB Output is correct
6 Correct 290 ms 254268 KB Output is correct
7 Correct 300 ms 254288 KB Output is correct
8 Correct 213 ms 254332 KB Output is correct
9 Correct 253 ms 254364 KB Output is correct
10 Correct 201 ms 254204 KB Output is correct
11 Correct 235 ms 254264 KB Output is correct
12 Correct 330 ms 254328 KB Output is correct
13 Correct 249 ms 254300 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 223 ms 254324 KB Output is correct
16 Correct 257 ms 254288 KB Output is correct
17 Correct 228 ms 254288 KB Output is correct
18 Correct 202 ms 254284 KB Output is correct
19 Correct 366 ms 254228 KB Output is correct
20 Correct 232 ms 254392 KB Output is correct
21 Correct 249 ms 254304 KB Output is correct
22 Correct 208 ms 254284 KB Output is correct
23 Correct 243 ms 254280 KB Output is correct
24 Correct 345 ms 254260 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 294 ms 254280 KB Output is correct
3 Correct 258 ms 254208 KB Output is correct
4 Correct 196 ms 254312 KB Output is correct
5 Correct 186 ms 254268 KB Output is correct
6 Correct 290 ms 254268 KB Output is correct
7 Correct 300 ms 254288 KB Output is correct
8 Correct 213 ms 254332 KB Output is correct
9 Correct 253 ms 254364 KB Output is correct
10 Correct 201 ms 254204 KB Output is correct
11 Correct 235 ms 254264 KB Output is correct
12 Correct 330 ms 254328 KB Output is correct
13 Correct 249 ms 254300 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 223 ms 254324 KB Output is correct
16 Correct 257 ms 254288 KB Output is correct
17 Correct 228 ms 254288 KB Output is correct
18 Correct 202 ms 254284 KB Output is correct
19 Correct 366 ms 254228 KB Output is correct
20 Correct 232 ms 254392 KB Output is correct
21 Correct 249 ms 254304 KB Output is correct
22 Correct 208 ms 254284 KB Output is correct
23 Correct 243 ms 254280 KB Output is correct
24 Correct 345 ms 254260 KB Output is correct
25 Correct 186 ms 253532 KB Output is correct
26 Correct 273 ms 254280 KB Output is correct
27 Correct 257 ms 254284 KB Output is correct
28 Correct 216 ms 254264 KB Output is correct
29 Correct 300 ms 254316 KB Output is correct
30 Correct 280 ms 254280 KB Output is correct
31 Correct 292 ms 254352 KB Output is correct
32 Correct 427 ms 254380 KB Output is correct
33 Correct 1352 ms 254204 KB Output is correct
34 Correct 1589 ms 254140 KB Output is correct
35 Correct 872 ms 254260 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12116 KB Output is correct
2 Correct 1431 ms 1973704 KB Output is correct
3 Correct 1246 ms 1980556 KB Output is correct
4 Correct 1320 ms 1982156 KB Output is correct
5 Correct 1406 ms 1982120 KB Output is correct
6 Correct 1332 ms 1980644 KB Output is correct
7 Correct 1343 ms 1978740 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 294 ms 254280 KB Output is correct
10 Correct 258 ms 254208 KB Output is correct
11 Correct 196 ms 254312 KB Output is correct
12 Correct 186 ms 254268 KB Output is correct
13 Correct 290 ms 254268 KB Output is correct
14 Correct 300 ms 254288 KB Output is correct
15 Correct 213 ms 254332 KB Output is correct
16 Correct 253 ms 254364 KB Output is correct
17 Correct 201 ms 254204 KB Output is correct
18 Correct 235 ms 254264 KB Output is correct
19 Correct 330 ms 254328 KB Output is correct
20 Correct 249 ms 254300 KB Output is correct
21 Correct 7 ms 12116 KB Output is correct
22 Correct 223 ms 254324 KB Output is correct
23 Correct 257 ms 254288 KB Output is correct
24 Correct 228 ms 254288 KB Output is correct
25 Correct 202 ms 254284 KB Output is correct
26 Correct 366 ms 254228 KB Output is correct
27 Correct 232 ms 254392 KB Output is correct
28 Correct 249 ms 254304 KB Output is correct
29 Correct 208 ms 254284 KB Output is correct
30 Correct 243 ms 254280 KB Output is correct
31 Correct 345 ms 254260 KB Output is correct
32 Correct 186 ms 253532 KB Output is correct
33 Correct 273 ms 254280 KB Output is correct
34 Correct 257 ms 254284 KB Output is correct
35 Correct 216 ms 254264 KB Output is correct
36 Correct 300 ms 254316 KB Output is correct
37 Correct 280 ms 254280 KB Output is correct
38 Correct 292 ms 254352 KB Output is correct
39 Correct 427 ms 254380 KB Output is correct
40 Correct 1352 ms 254204 KB Output is correct
41 Correct 1589 ms 254140 KB Output is correct
42 Correct 872 ms 254260 KB Output is correct
43 Correct 3 ms 7124 KB Output is correct
44 Correct 7 ms 12104 KB Output is correct
45 Correct 1778 ms 1985360 KB Output is correct
46 Correct 1412 ms 1980752 KB Output is correct
47 Correct 1480 ms 1981308 KB Output is correct
48 Correct 1321 ms 1983348 KB Output is correct
49 Correct 1981 ms 1985500 KB Output is correct
50 Correct 1356 ms 1983012 KB Output is correct
51 Correct 1313 ms 1983484 KB Output is correct
52 Correct 1303 ms 1981012 KB Output is correct
53 Correct 2734 ms 1981844 KB Output is correct
54 Correct 2973 ms 1982968 KB Output is correct
55 Correct 2864 ms 1981892 KB Output is correct
56 Correct 2960 ms 1982608 KB Output is correct
57 Correct 3015 ms 1982584 KB Output is correct
58 Correct 3475 ms 1982788 KB Output is correct
59 Correct 3219 ms 1983088 KB Output is correct
60 Correct 2629 ms 1982224 KB Output is correct
61 Correct 2335 ms 1981996 KB Output is correct