Submission #599534

#	Time	Username	Problem	Language	Result	Execution time	Memory
599534		definitelynotmee	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7071 ms	680220 KiB

dungeons

    #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 (stderr)

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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11