oj.uz

Submission #443405

# Submission time Handle Problem Language Result Execution time Memory
443405 2021-07-10T12:58:03 Z azberjibiou Dungeons Game (IOI21_dungeons) C++17
25 / 100
 7000 ms 146512 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mxN=50050;
const ll INF=1000000000;
ll N, K;
ll S[mxN], P[mxN], W[mxN], L[mxN];
pll adj[mxN];
vector <ll> coor;
pll sps[mxN][30][6];
 
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N=n;
	for(int i=0;i<N;i++)    S[i]=s[i], P[i]=p[i], W[i]=w[i], L[i]=l[i];
	for(int i=0;i<N;i++)    coor.push_back(S[i]);
	sort(coor.begin(), coor.end());
	coor.erase(unique(coor.begin(), coor.end()), coor.end());
	K=coor.size();
	sort(coor.begin(), coor.end());
	for(int i=0;i<N;i++)    adj[i]={L[i], P[i]};
	adj[N]={N, 0};
	for(int i=0;i<=K;i++)
    {
        for(int j=0;j<=N;j++)    sps[j][0][i]=adj[j];
        for(int j=1;j<30;j++)
        {
            for(int k=0;k<=N;k++)
            {
                sps[k][j][i].fir=sps[sps[k][j-1][i].fir][j-1][i].fir;
                sps[k][j][i].sec=sps[sps[k][j-1][i].fir][j-1][i].sec+sps[k][j-1][i].sec;
            }
        }
        if(i==K)    break;
        for(int j=0;j<N;j++)
        {
            if(S[j]<=coor[i])   adj[j]={W[j], S[j]};
            else    adj[j]={L[j], P[j]};
        }
    }
	return;
}
 
long long simulate(int x, int z) {
    ll ans=z;
	for(int i=0;i<K;i++)
    {
        if(ans>=coor[i])    continue;
        for(int j=29;j>=0;j--)
        {
            if(sps[x][j][i].sec+ans>=coor[i])    continue;
            ans+=sps[x][j][i].sec;
            x=sps[x][j][i].fir;
        }
        if(x==N)    return ans;
        ans+=sps[x][0][i].sec;
        x=sps[x][0][i].fir;
        if(x==N)    return ans;
    }
    ans+=sps[x][29][K].sec;
    return ans;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 3240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3148 KB Output is correct
2 Correct 206 ms 146420 KB Output is correct
3 Correct 193 ms 146420 KB Output is correct
4 Correct 172 ms 146468 KB Output is correct
5 Correct 186 ms 146492 KB Output is correct
6 Correct 188 ms 146512 KB Output is correct
7 Correct 223 ms 146384 KB Output is correct
8 Correct 189 ms 146512 KB Output is correct
9 Correct 204 ms 146368 KB Output is correct
10 Correct 243 ms 146388 KB Output is correct
11 Correct 199 ms 146508 KB Output is correct
12 Correct 304 ms 146384 KB Output is correct
13 Correct 437 ms 146412 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3148 KB Output is correct
2 Correct 206 ms 146420 KB Output is correct
3 Correct 193 ms 146420 KB Output is correct
4 Correct 172 ms 146468 KB Output is correct
5 Correct 186 ms 146492 KB Output is correct
6 Correct 188 ms 146512 KB Output is correct
7 Correct 223 ms 146384 KB Output is correct
8 Correct 189 ms 146512 KB Output is correct
9 Correct 204 ms 146368 KB Output is correct
10 Correct 243 ms 146388 KB Output is correct
11 Correct 199 ms 146508 KB Output is correct
12 Correct 304 ms 146384 KB Output is correct
13 Correct 437 ms 146412 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct
15 Correct 267 ms 146420 KB Output is correct
16 Correct 316 ms 146508 KB Output is correct
17 Correct 293 ms 146364 KB Output is correct
18 Correct 379 ms 146332 KB Output is correct
19 Correct 422 ms 146420 KB Output is correct
20 Correct 339 ms 146420 KB Output is correct
21 Correct 429 ms 146364 KB Output is correct
22 Correct 294 ms 146416 KB Output is correct
23 Correct 354 ms 146424 KB Output is correct
24 Correct 536 ms 146424 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3148 KB Output is correct
2 Correct 206 ms 146420 KB Output is correct
3 Correct 193 ms 146420 KB Output is correct
4 Correct 172 ms 146468 KB Output is correct
5 Correct 186 ms 146492 KB Output is correct
6 Correct 188 ms 146512 KB Output is correct
7 Correct 223 ms 146384 KB Output is correct
8 Correct 189 ms 146512 KB Output is correct
9 Correct 204 ms 146368 KB Output is correct
10 Correct 243 ms 146388 KB Output is correct
11 Correct 199 ms 146508 KB Output is correct
12 Correct 304 ms 146384 KB Output is correct
13 Correct 437 ms 146412 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct
15 Correct 267 ms 146420 KB Output is correct
16 Correct 316 ms 146508 KB Output is correct
17 Correct 293 ms 146364 KB Output is correct
18 Correct 379 ms 146332 KB Output is correct
19 Correct 422 ms 146420 KB Output is correct
20 Correct 339 ms 146420 KB Output is correct
21 Correct 429 ms 146364 KB Output is correct
22 Correct 294 ms 146416 KB Output is correct
23 Correct 354 ms 146424 KB Output is correct
24 Correct 536 ms 146424 KB Output is correct
25 Execution timed out 7067 ms 145612 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 3240 KB Output isn't correct
2 Halted 0 ms 0 KB -