제출 #1126913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126913		fgdsa	던전 (IOI21_dungeons)	C++20	89 / 100	5902 ms	1490560 KiB

dungeons

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

using namespace std;

#define ll long long
#define para pair<ll, ll>

const ll LOG = 12;
const ll LOG2 = 13;
const ll MAXN = 400000+1534;
const ll INF = 1e18+7;

struct Str{
	int v;
	ll sum;
	ll mn;
};

Str jump[MAXN][LOG][LOG2];

int n;
vector<ll> s;
vector<ll> p;
vector<int> w;
vector<int> l;

Str operacjaLacznia(const Str a, const Str b){
	Str res;
	res.v = b.v;
	res.sum = a.sum + b.sum;
	res.mn = min(a.mn, b.mn - a.sum);
	return res;
}

void gen(ll x, ll h){

	for(int i = 0; i < n; ++i){
		if(h < s[i]){
			jump[i][0][x] = {l[i], p[i], s[i]};
		}
		else{
			// if(i == n-1){
			// 	jump[i][0][x] = {w[i], s[i], INF};
			// }
			jump[i][0][x] = {w[i], s[i], INF};
		}
	}
	jump[n][0][x] = {n, 0, INF};

	for(int i = 1; i < LOG; ++i){
		for(int j = 0; j < n; ++j){
			Str cur = jump[j][i-1][x];
			cur = operacjaLacznia(cur, jump[cur.v][i-1][x]);
			cur = operacjaLacznia(cur, jump[cur.v][i-1][x]);
			cur = operacjaLacznia(cur, jump[cur.v][i-1][x]);

			jump[j][i][x] = cur;
			// if(x == 1 && i == 1 && j == 0){
			// 	cerr << jump[j][i-1][x].v << " " << jump[j][i-1][x].sum << " " << jump[j][i-1][x].mn << "\n";
			// 	cerr << jump[jump[j][i-1][x].v][i-1][x].mn << "\n";
			// 	cerr << cur.v << " " << cur.sum << " " << cur.mn << "\n";
			// }
		}
	}
	return;
}


void init(int nT, vector<int> sT, vector<int> pT, vector<int> wT, vector<int> lT){
	n = nT;
	for(auto i : sT) s.push_back(i);
	s.shrink_to_fit();
	for(auto i : pT) p.push_back(i);
	p.shrink_to_fit();
	for(auto i : wT) w.push_back(i);
	w.shrink_to_fit();
	for(auto i : lT) l.push_back(i);
	l.shrink_to_fit();
	
	ll h = 1;
	for(int i = 0; i < LOG2; ++i){
		gen(i, h);
		h *= 4;
	}
	
	return;
}

ll simulate(int x, int zT) {
	ll z = zT;
	ll cnt = 0;
	while(x != n){
		ll pot2 = 1;
		ll wyk = 0;
		while(pot2 * 4 <= z) pot2*=4, ++wyk;

		for(int j = LOG-1; j >= 0; --j){
			// cerr << j << ":\n";
			// cerr << "	" << x << " " << z << " " << pot2 << ": " << jump[x][j][wyk].v << " " << jump[x][j][wyk].mn << " " << jump[x][j][wyk].sum << '\n';
			if(jump[x][j][wyk].mn > z){
				z += jump[x][j][wyk].sum;
				x = jump[x][j][wyk].v;
			}
			if(jump[x][j][wyk].mn > z){
				z += jump[x][j][wyk].sum;
				x = jump[x][j][wyk].v;
			}
			if(jump[x][j][wyk].mn > z){
				z += jump[x][j][wyk].sum;
				x = jump[x][j][wyk].v;
			}
		}	
		if(x == n) break;

		z += s[x];
		x = w[x];
		// if(++cnt == 5){ 
		// 	cerr << "\n";
		// 	return 0;
		// }
	}


	return z;
}

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