Submission #1243397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243397		guanex	Dungeons Game (IOI21_dungeons)	C++20	24 / 100	7091 ms	67732 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int N;
int win[50005][25];//endpoint of win streak
ll stopwin[50005][25];//max on the range
ll winsum[50005][25];//sum of the win streak
ll lose[50005][25]; // endpoint of lose streak
ll stoplose[50005][25]; // min on the range
ll losesum[50005][25]; // sum of teh lose streak
int v[50005];

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){
		v[i] = s[i];
		winsum[i][0] = s[i];
		losesum[i][0] = p[i];
		win[i][0] = w[i];
		lose[i][0] = l[i];
		if(w[i] == n){
			stopwin[i][0] = 1e16;
		}else
			stopwin[i][0] = max(s[i] + s[i], s[w[i]]);
		if(l[i] == n){
			stoplose[i][0] = -1;
		}else
			stoplose[i][0] = min(s[i] + p[i], s[l[i]]);
	}
	win[n][0] = n;
	lose[n][0] = n;
	winsum[n][0] = 0;
	losesum[n][0] = 0;
	stopwin[n][0] = 1e16;
	stoplose[n][0] = -1;
	for(int j = 1; j < 25; ++j){
		for(int i = 0; i < n; ++i){
			win[i][j] = win[win[i][j-1]][j-1];
			lose[i][j] = lose[lose[i][j-1]][j-1];
			winsum[i][j] = winsum[i][j-1] + winsum[win[i][j-1]][j-1];
			if(winsum[i][j] > 10000000000000000){
				winsum[i][j] = 10000000000000000;
			}
			losesum[i][j] = losesum[i][j-1] + losesum[lose[i][j-1]][j-1];
			if(losesum[i][j] > 10000000000000000){
				losesum[i][j] = 10000000000000000;
			}
			stopwin[i][j] = max(stopwin[i][j-1] + winsum[win[i][j-1]][j-1], stopwin[win[i][j-1]][j-1]);
			stoplose[i][j] = min(stoplose[i][j-1] + losesum[lose[i][j-1]][j-1], stoplose[lose[i][j-1]][j-1]);
		}
	}
	return;
}

ll checkwin(int no, ll &s){
	for(int i = 24; i >= 0; --i){
		ll ns = s + winsum[no][i];
		if(stopwin[no][i] > ns){
			continue;
		}
		//cout << stopwin[no][i] << " ";
		s += winsum[no][i];
		no = win[no][i];
		//cout << no << " " << s<< endl;
	}
	s += winsum[no][0];
	return win[no][0];
}

ll checklose(int no, ll &s){
	//cout << no << " " << s << endl;
	for(int i = 24; i >= 0; --i){
		ll ns = s + losesum[no][i];
		//cout << stoplose[no][i] << " " << no << " " << ns << " " << i << endl;
		if(stoplose[no][i] <= ns){
			continue;
		}
		//cout << stoplose[no][i] << " ";
		s += losesum[no][i];
		no = lose[no][i];
		//cout << no << " " << s << endl;
	}
	s += losesum[no][0];
	//cout << lose[no][0] << " " << s << endl;
	return lose[no][0];
}

long long simulate(int x, int z) {
	//cout << stoplose[0][0] << " " << stoplose[1][1] << endl;
	int no = x;
	ll s = z;
	bool parity = 0; //0 -> starts losing 1 -> starts winning
	if(z >= v[x]){
		parity = 1;
	}
	while(no != N){
		//cout << no << endl;
		// i get my new endpoint after the win/lose streak
		//cout << parity << " " << no << " " << s << " im trying bro" << endl;
		if(parity == 1){
			no = checkwin(no, s);
			parity = 0;
		}else{
			no = checklose(no, s);
			parity = 1;
		}
		//cout << no << " " << s << endl;
	}
	return s;
}

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