oj.uz

Submission #440157

# Submission time Handle Problem Language Result Execution time Memory
440157 2021-07-01T16:30:59 Z algorithm16 Dungeons Game (IOI21_dungeons) C++17
24 / 100
 7000 ms 60756 KB 
#include "dungeons.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
vector <llint> s1,p1,w1,l1;
llint nxtl[50005][35],nxtw[50005][35],sum[50005][35],sumw[50005][35];
llint n1,b1=1;
void init(int n,std::vector<int> s,std::vector<int> p,std::vector<int> w,std::vector<int> l) {
	n1=n;
	for(int i=0;i<n;i++) {
		s1.push_back(s[i]);
		p1.push_back(p[i]);
		w1.push_back(w[i]);
		l1.push_back(l[i]);
	}
	nxtl[n][0]=n;
	nxtw[n][0]=n;
	for(int i=0;i<n;i++) {
		nxtl[i][0]=l[i];
		nxtw[i][0]=w[i];
		sum[i][0]=p[i];
		sumw[i][0]=s[i];
		if(i<n-1 && s[i]!=s[i+1]) b1=0;
	}
	for(int i=1;i<30;i++) {
		for(int j=0;j<=n;j++) {
			nxtl[j][i]=nxtl[nxtl[j][i-1]][i-1];
			nxtw[j][i]=nxtw[nxtw[j][i-1]][i-1];
			sum[j][i]=sum[j][i-1]+sum[nxtl[j][i-1]][i-1];
			sumw[j][i]=sumw[j][i-1]+sumw[nxtw[j][i-1]][i-1];
		}
	}
	return;
}
pair <int,llint> get(int x,int v) {
	llint ret=0;
	for(int i=0;i<30;i++) {
		if(v & (1 << i)) {
			ret+=sum[x][i];
			x=nxtl[x][i];
		}
	}
	return make_pair(x,ret);
}
pair <int,llint> getw(int x,int v) {
	llint ret=0;
	for(int i=0;i<30;i++) {
		if(v & (1 << i)) {
			ret+=sumw[x][i];
			x=nxtw[x][i];
		}
	}
	return make_pair(x,ret);
}
long long simulate(int x, int z) {
	if(x==n1) return z;
	if(b1) {
		llint lo=0,hi=1e9;
		while(lo<hi) {
			llint mid=(lo+hi)/2;
			//cout << lo << " " << hi << " " << mid << " " << get(x,mid).first << " " << get(x,mid).second << "\n";
			if(z+get(x,mid).second>=s1[get(x,mid).first]) hi=mid;
			else lo=mid+1;
		}
		llint ret=get(x,lo).second;
		x=get(x,lo).first;
		lo=0;
		hi=1e9;
		while(lo<hi) {
			llint mid=(lo+hi)/2;
			if(getw(x,mid).first==n1) hi=mid;
			else lo=mid+1;
		}
		ret+=getw(x,lo).second;
		return z+ret;
	}
	llint ret=z;
	while(x!=n1) {
		if(ret<s1[x]) {
			ret+=p1[x];
			x=l1[x];
		}
		else {
			ret+=s1[x];
			x=w1[x];
		}
	}
	return ret;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 3 ms 2672 KB Output is correct
4 Correct 124 ms 59416 KB Output is correct
5 Correct 3 ms 2620 KB Output is correct
6 Correct 124 ms 59324 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Runtime error 220 ms 54864 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1500 KB Output is correct
2 Correct 734 ms 60620 KB Output is correct
3 Correct 1024 ms 60700 KB Output is correct
4 Correct 1173 ms 60204 KB Output is correct
5 Correct 1072 ms 60188 KB Output is correct
6 Correct 758 ms 60412 KB Output is correct
7 Correct 774 ms 60376 KB Output is correct
8 Correct 1347 ms 60080 KB Output is correct
9 Correct 765 ms 60160 KB Output is correct
10 Correct 1199 ms 59956 KB Output is correct
11 Correct 1145 ms 60392 KB Output is correct
12 Correct 2585 ms 60432 KB Output is correct
13 Correct 2020 ms 60332 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1500 KB Output is correct
2 Correct 734 ms 60620 KB Output is correct
3 Correct 1024 ms 60700 KB Output is correct
4 Correct 1173 ms 60204 KB Output is correct
5 Correct 1072 ms 60188 KB Output is correct
6 Correct 758 ms 60412 KB Output is correct
7 Correct 774 ms 60376 KB Output is correct
8 Correct 1347 ms 60080 KB Output is correct
9 Correct 765 ms 60160 KB Output is correct
10 Correct 1199 ms 59956 KB Output is correct
11 Correct 1145 ms 60392 KB Output is correct
12 Correct 2585 ms 60432 KB Output is correct
13 Correct 2020 ms 60332 KB Output is correct
14 Correct 3 ms 1484 KB Output is correct
15 Correct 212 ms 60532 KB Output is correct
16 Correct 165 ms 60756 KB Output is correct
17 Correct 1707 ms 60204 KB Output is correct
18 Correct 1883 ms 60248 KB Output is correct
19 Execution timed out 7099 ms 60304 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1500 KB Output is correct
2 Correct 734 ms 60620 KB Output is correct
3 Correct 1024 ms 60700 KB Output is correct
4 Correct 1173 ms 60204 KB Output is correct
5 Correct 1072 ms 60188 KB Output is correct
6 Correct 758 ms 60412 KB Output is correct
7 Correct 774 ms 60376 KB Output is correct
8 Correct 1347 ms 60080 KB Output is correct
9 Correct 765 ms 60160 KB Output is correct
10 Correct 1199 ms 59956 KB Output is correct
11 Correct 1145 ms 60392 KB Output is correct
12 Correct 2585 ms 60432 KB Output is correct
13 Correct 2020 ms 60332 KB Output is correct
14 Correct 3 ms 1484 KB Output is correct
15 Correct 212 ms 60532 KB Output is correct
16 Correct 165 ms 60756 KB Output is correct
17 Correct 1707 ms 60204 KB Output is correct
18 Correct 1883 ms 60248 KB Output is correct
19 Execution timed out 7099 ms 60304 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Runtime error 220 ms 54864 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -