Submission #809065

#	Time	Username	Problem	Language	Result	Execution time	Memory
809065		Benmath	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	117 ms	77932 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>s;
vector<int>p;
vector<int>l;
vector<int>w;
long long int type[7][400001][31];
int loc[7][400001][31];
int k=1;
int tip[10000001];
vector<long long int>tipovi;
void init(int n1, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1) {
    n=n1;
    
    for(int i=0;i<n;i++){
        s.push_back(s1[i]);
        p.push_back(p1[i]);
        w.push_back(w1[i]);
        l.push_back(l1[i]);
        }
    sort(s1.begin(),s1.end());
    tipovi.push_back(s1[0]);
    tip[s1[0]]=0;
            for(int i=1;i<n;i++){
                if(s1[i]>s1[i-1]){
                    tipovi.push_back(s1[i]);
                    tip[s1[i]]=k;
                    k++;
                }
            }
         
    for(int t=0;t<=k;t++){
        for(int j=0;j<=30;j++){
            for(int i=n;i>=0;i--){
                if(i==n){
                    type[t][i][j]=0;
                    loc[t][i][j]=n;
                }else{
                    if(j==0){
                        int ro=tip[s1[i]];
                        if(t>ro){
                            type[t][i][j]=s[i];
                            loc[t][i][j]=w[i];
                        }else{
                            type[t][i][j]=p[i];
                            loc[t][i][j]=l[i];
                        }
                    }else{
                        loc[t][i][j]=loc[t][loc[t][i][j-1]][j-1];
                        type[t][i][j]=type[t][i][j-1]+type[t][loc[t][i][j-1]][j-1];
                    }
                }
            }
        }
    }
    
}

long long simulate(int x, int z) {
   
	int neki;
	int t1=0;
	long long int total=z;
	int lok=x;
	while(t1==0){
	    if(total<tipovi[0]){
	        neki=0;
	    }
	    int ro=tipovi.size();
	    if(total>=tipovi[ro-1]){
	        neki=ro;
	        return (total+type[neki][lok][30]);
	    }
	    for(int i=0;i<ro;i++){
	        if(i!=(ro-1)){
	            if(total>=tipovi[i] and total<tipovi[i+1]){
	                neki=i+1;
	            }
	        }
	    }
	    for(int j=30;j>=0;j--){
	        if((total+type[neki][lok][j])<tipovi[neki]){
	            total=total+type[neki][lok][j];
	            lok=loc[neki][lok][j];
	        }
	    }
	    total=total+type[neki][lok][0];
	    lok=loc[neki][lok][0];
	    if(lok==n){
	        return total;
	    }
	   
	}
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^
dungeons.cpp:90:9: warning: 'neki' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |      lok=loc[neki][lok][0];
      |      ~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11