oj.uz

Submission #599534

# Submission time Handle Problem Language Result Execution time Memory
599534 2022-07-19T15:17:06 Z definitelynotmee Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 680220 KB 
    #include "dungeons.h"
    #include<bits/stdc++.h>
    using namespace std;
    #define ff first
    #define ss second
    #define all(x) x.begin(), x.end()
    using ll = long long;
    using pii = pair<int,int>;
    using pll = pair<ll,ll>;
    template<typename T>
    using matrix= vector<vector<T>>;
    const int T = 5000;
     
    struct jmp{
    	ll to, plus, win;
    	jmp merge(jmp b){
    		jmp ret;
    		ret.to = b.to;
    		ret.plus = plus+b.plus;
    		ret.win = min(win,b.win-plus);
    		return ret;
    	}
    };
     
    jmp lift[24][24][50000];
    matrix<jmp> lift2;
    vector<ll> windp;
    int N;
    vector<int> S, P, W, L;
     
    void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    	N = n;
    	S =s;
    	P = p;
    	W = w;
    	L = l;
     
    	int t = T;
    	if(N > 5e4){
    		lift2 = matrix<jmp>(int(log2(T)+1),vector<jmp>(n));
    		for(int i = 0; i < n; i++){
    			if(s[i] <= T){
    				lift2[0][i] = {w[i],s[i],1ll<<60};
    				if(w[i] == n){
    					lift2[0][i].win = 0, lift2[0][i].to = i;
    				}
    			} else {lift2[0][i] = {l[i],p[i],s[i]};
    				if(l[i] == n)
    					lift2[0][i].win = 0, lift2[0][i].to = i;
    			}
    		}
    		for(int i = 1; i < lift2.size(); i++){
    			for(int j = 0; j < n; j++)
    				lift2[i][j] = lift2[i-1][j].merge(lift2[i-1][lift2[i-1][j].to]);
    		}
    	} else {
    		for(int x = 0; x < 24; x++){
    			for(int i = 0; i < n; i++){
    				if(s[i] <= t){
    					lift[x][0][i] = {w[i],s[i],1ll<<60};
    					if(w[i] == n){
    						lift[x][0][i].win = 0, lift[x][0][i].to = i;
    					}
    				} else {lift[x][0][i] = {l[i],p[i],s[i]};
    					if(l[i] == n)
    						lift[x][0][i].win = 0, lift[x][0][i].to = i;
    				}
    			}
    			for(int i = 1; i < 24; i++){
    				for(int j = 0; j < n; j++)
    					lift[x][i][j] = lift[x][i-1][j].merge(lift[x][i-1][lift[x][i-1][j].to]);
    			}
    			t*=2;
    		}
    	}
     
     
    	windp = vector<ll>(n+1);
    	for(int i = n-1; i >= 0; i--)
    		windp[i] = windp[w[i]]+s[i];
     
    	return;
    }
     
    long long simulate(int x, int Z) {
     
    	ll z = Z;
    	int it = T;
     
    	while(it-- && x != N){
    		if(S[x] <= z){
    			z+=S[x];
    			x=W[x];
    		} else {
    			z+=P[x];
    			x=L[x];
    		}
    	}
    	if(N > 5e4){
    		while(x!=N && z < int(1e7)){
    			for(int i = int(lift2.size())-1; i>= 0; i--){
    				if(lift2[i][x].win > z){
    					z+=lift2[i][x].plus;
    					x = lift2[i][x].to;
    				}
    			}
    			if(S[x] <= z){
    				z+=S[x];
    				x=W[x];
    			} else {
    				z+=P[x];
    				x=L[x];
    			}
    		}
    	} else {
    		int power = 0;
    		while(x!=N && z < int(1e7)){
    			while(z >= T*(1<<power+1) && power < 23)
    				power++;
    			for(int i = 23; i>= 0; i--){
    				if(lift[power][i][x].win > z){
    					z+=lift[power][i][x].plus;
    					x = lift[power][i][x].to;
    				}
    			}
    			if(S[x] <= z){
    				z+=S[x];
    				x=W[x];
    			} else {
    				z+=P[x];
    				x=L[x];
    			}
    		}
    	}
     
     
    	return z+windp[x];
    }

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<jmp, std::allocator<jmp> >, std::allocator<std::vector<jmp, std::allocator<jmp> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for(int i = 1; i < lift2.size(); i++){
      |                      ~~^~~~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:118:30: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  118 |        while(z >= T*(1<<power+1) && power < 23)
      |                         ~~~~~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 17 ms 30932 KB Output is correct
4 Correct 306 ms 679244 KB Output is correct
5 Correct 14 ms 30932 KB Output is correct
6 Correct 329 ms 679296 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17388 KB Output is correct
2 Correct 2048 ms 151288 KB Output is correct
3 Correct 2645 ms 151344 KB Output is correct
4 Correct 959 ms 151364 KB Output is correct
5 Correct 246 ms 151352 KB Output is correct
6 Correct 2625 ms 151364 KB Output is correct
7 Correct 4122 ms 151344 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17364 KB Output is correct
2 Correct 374 ms 680040 KB Output is correct
3 Correct 909 ms 680144 KB Output is correct
4 Correct 990 ms 680108 KB Output is correct
5 Correct 942 ms 680140 KB Output is correct
6 Correct 1470 ms 680072 KB Output is correct
7 Correct 1124 ms 680180 KB Output is correct
8 Correct 913 ms 680052 KB Output is correct
9 Correct 329 ms 680068 KB Output is correct
10 Correct 967 ms 680028 KB Output is correct
11 Correct 2864 ms 680216 KB Output is correct
12 Correct 3135 ms 680120 KB Output is correct
13 Correct 1038 ms 680048 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17364 KB Output is correct
2 Correct 374 ms 680040 KB Output is correct
3 Correct 909 ms 680144 KB Output is correct
4 Correct 990 ms 680108 KB Output is correct
5 Correct 942 ms 680140 KB Output is correct
6 Correct 1470 ms 680072 KB Output is correct
7 Correct 1124 ms 680180 KB Output is correct
8 Correct 913 ms 680052 KB Output is correct
9 Correct 329 ms 680068 KB Output is correct
10 Correct 967 ms 680028 KB Output is correct
11 Correct 2864 ms 680216 KB Output is correct
12 Correct 3135 ms 680120 KB Output is correct
13 Correct 1038 ms 680048 KB Output is correct
14 Correct 11 ms 17364 KB Output is correct
15 Correct 392 ms 680048 KB Output is correct
16 Correct 388 ms 680104 KB Output is correct
17 Correct 911 ms 680220 KB Output is correct
18 Correct 938 ms 680048 KB Output is correct
19 Correct 1416 ms 680012 KB Output is correct
20 Correct 1006 ms 680028 KB Output is correct
21 Correct 1033 ms 680084 KB Output is correct
22 Correct 1430 ms 680032 KB Output is correct
23 Correct 3060 ms 680056 KB Output is correct
24 Correct 3315 ms 680044 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17364 KB Output is correct
2 Correct 374 ms 680040 KB Output is correct
3 Correct 909 ms 680144 KB Output is correct
4 Correct 990 ms 680108 KB Output is correct
5 Correct 942 ms 680140 KB Output is correct
6 Correct 1470 ms 680072 KB Output is correct
7 Correct 1124 ms 680180 KB Output is correct
8 Correct 913 ms 680052 KB Output is correct
9 Correct 329 ms 680068 KB Output is correct
10 Correct 967 ms 680028 KB Output is correct
11 Correct 2864 ms 680216 KB Output is correct
12 Correct 3135 ms 680120 KB Output is correct
13 Correct 1038 ms 680048 KB Output is correct
14 Correct 11 ms 17364 KB Output is correct
15 Correct 392 ms 680048 KB Output is correct
16 Correct 388 ms 680104 KB Output is correct
17 Correct 911 ms 680220 KB Output is correct
18 Correct 938 ms 680048 KB Output is correct
19 Correct 1416 ms 680012 KB Output is correct
20 Correct 1006 ms 680028 KB Output is correct
21 Correct 1033 ms 680084 KB Output is correct
22 Correct 1430 ms 680032 KB Output is correct
23 Correct 3060 ms 680056 KB Output is correct
24 Correct 3315 ms 680044 KB Output is correct
25 Correct 343 ms 679304 KB Output is correct
26 Correct 387 ms 680128 KB Output is correct
27 Correct 360 ms 680188 KB Output is correct
28 Correct 451 ms 680112 KB Output is correct
29 Correct 399 ms 680152 KB Output is correct
30 Correct 1053 ms 680112 KB Output is correct
31 Correct 1155 ms 680064 KB Output is correct
32 Correct 4755 ms 680068 KB Output is correct
33 Correct 559 ms 680100 KB Output is correct
34 Correct 2272 ms 680048 KB Output is correct
35 Correct 1265 ms 680088 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17388 KB Output is correct
2 Correct 2048 ms 151288 KB Output is correct
3 Correct 2645 ms 151344 KB Output is correct
4 Correct 959 ms 151364 KB Output is correct
5 Correct 246 ms 151352 KB Output is correct
6 Correct 2625 ms 151364 KB Output is correct
7 Correct 4122 ms 151344 KB Output is correct
8 Correct 9 ms 17364 KB Output is correct
9 Correct 374 ms 680040 KB Output is correct
10 Correct 909 ms 680144 KB Output is correct
11 Correct 990 ms 680108 KB Output is correct
12 Correct 942 ms 680140 KB Output is correct
13 Correct 1470 ms 680072 KB Output is correct
14 Correct 1124 ms 680180 KB Output is correct
15 Correct 913 ms 680052 KB Output is correct
16 Correct 329 ms 680068 KB Output is correct
17 Correct 967 ms 680028 KB Output is correct
18 Correct 2864 ms 680216 KB Output is correct
19 Correct 3135 ms 680120 KB Output is correct
20 Correct 1038 ms 680048 KB Output is correct
21 Correct 11 ms 17364 KB Output is correct
22 Correct 392 ms 680048 KB Output is correct
23 Correct 388 ms 680104 KB Output is correct
24 Correct 911 ms 680220 KB Output is correct
25 Correct 938 ms 680048 KB Output is correct
26 Correct 1416 ms 680012 KB Output is correct
27 Correct 1006 ms 680028 KB Output is correct
28 Correct 1033 ms 680084 KB Output is correct
29 Correct 1430 ms 680032 KB Output is correct
30 Correct 3060 ms 680056 KB Output is correct
31 Correct 3315 ms 680044 KB Output is correct
32 Correct 343 ms 679304 KB Output is correct
33 Correct 387 ms 680128 KB Output is correct
34 Correct 360 ms 680188 KB Output is correct
35 Correct 451 ms 680112 KB Output is correct
36 Correct 399 ms 680152 KB Output is correct
37 Correct 1053 ms 680112 KB Output is correct
38 Correct 1155 ms 680064 KB Output is correct
39 Correct 4755 ms 680068 KB Output is correct
40 Correct 559 ms 680100 KB Output is correct
41 Correct 2272 ms 680048 KB Output is correct
42 Correct 1265 ms 680088 KB Output is correct
43 Correct 2 ms 3924 KB Output is correct
44 Correct 11 ms 17492 KB Output is correct
45 Correct 340 ms 162984 KB Output is correct
46 Correct 278 ms 158412 KB Output is correct
47 Correct 572 ms 158752 KB Output is correct
48 Correct 890 ms 160936 KB Output is correct
49 Correct 375 ms 162980 KB Output is correct
50 Correct 2411 ms 160552 KB Output is correct
51 Correct 929 ms 160976 KB Output is correct
52 Correct 2453 ms 158628 KB Output is correct
53 Execution timed out 7071 ms 159436 KB Time limit exceeded
54 Halted 0 ms 0 KB -