제출 #1179587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179587		Gr1sen	Dungeons Game (IOI21_dungeons)	C++20	13 / 100	376 ms	27424 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pi pair<ll, ll>
#define vp vector<pi>
#define vvp vector<vp>

struct node {
	ll max = -1;
	ll to = -1;
	ll gain = -1;
	void print() {
		cerr << "node : {max : " << max << ", to : " << to << ", gain : " << gain << "}\n";
	}
};

int n;
vi S, P, W, L;
vl M, M2, M3;
vector<vector<node>> BL;

void print(vi &L1) {
	cerr << "{";
	for (auto i : L1) {
		cerr << i << ", ";
	}
	cerr << "}\n";
}

void print(vl &L1) {
	cerr << "{";
	for (auto i : L1) {
		cerr << i << ", ";
	}
	cerr << "}\n";
}

void print(vector<vector<node>> &L1) {
	cerr << "{\n";
	for (auto i : L1) {
		cerr << "{\n";
		for (auto j : i) {
			j.print();
		}
		cerr << "},\n";
	}
	cerr << "}\n";
}

ll oinkoink(int p) {
	if (p == n) return 0;
	if (M[p] != -1) return M[p];
	return M[p] = oinkoink(W[p]) + 1;
}

ll oinkoinkoink(int p, ll z) {
	if (p == n) return -1;
	if (M2[p] != -1) return -1;
	if (M3[p] != -1) {
		return M2[p] = z - M3[p];
	}
	M3[p] = z;
	ll a = oinkoinkoink(L[p], z + P[p]);
	if (a == -1) {
		M2[p] = -2;
		return -1;
	}
	if (M2[p] != -1) {
		return -1;
	}
	M2[p] = a;
	return a;
}

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;
	M = vl(n, -1);
	M2 = vl(n, -1);
	BL = vector<vector<node>>(n, vector<node>(log2(n)+2));
	for (int i = 0; i < n; i++) oinkoink(i);
	for (int i = 0; i < n; i++) {
		M3 = vl(n, -1);
		oinkoinkoink(i, 0);
	}
	for (int i = 0; i < n; i++) {
		BL[i][0] = {S[i], L[i], P[i]};
	}
	for (int j = 1; j < BL[0].size(); j++) {
		//cerr << j << endl;
		for (int i = 0; i < n; i++) {
			//if (i == 32) cerr << "i : " << i << endl;
			ll to = BL[i][j-1].to;
			//if (i == 32) cerr << "to : " << to << endl;
			if (to == -1 || to == n || BL[i][j-1].max == -1) continue;
			//if (i == 32) cerr << "BL[to][j-1].max - BL[i][j-1].gain : " << (BL[to][j-1].max - BL[i][j-1].gain) << endl;
			//if (i == 32) cerr << "BL[to][j-1].to : " << BL[to][i-1].to << endl;
			//if (i == 32) cerr << "BL[to][j-1].gain + BL[i][j-1].gain : " << (BL[to][j-1].gain + BL[i][j-1].gain) << endl;
			BL[i][j] = {max(BL[to][j-1].max - BL[i][j-1].gain, (ll)-1), BL[to][j-1].to, BL[to][j-1].gain + BL[i][j-1].gain};
		}
	}
	/*
	cerr << "M : ";
	print(M);
	cerr << "M2 : ";
	print(M2);
	cerr << "M3 : ";
	print(M3); 
	cerr << "BL : ";
	print(BL);
	//*/
	return;
}

ll oink(ll x, ll z);

ll oinkoinkoinkoink(ll x, ll z) {
	//cerr << "oinkoinkoinkoink(" << x << ", " << z << ")" << endl;
	for (int i = BL[x].size()-1; i > -1; i--) {
		if (z >= BL[x][i].max || BL[x][i].max == -1) continue;
		return oink(BL[x][i].to, z + BL[x][i].gain);
	}
	return oink(L[x], z + P[x]);
}

ll oink(ll x, ll z) {
	//cerr << "oink(" << x << ", " << z <<")" << endl;
	if (x == n) return z;
	if (z >= S[0]) return z + M[x]*S[0];
	if (M2[x] == -2) return oinkoinkoinkoink(x, z);
	//cerr << "S[0]-z-1 : " << S[0]-z-1 << ", M2[x] : " << M2[x] << ", ((S[0]-z-1)/M2[x])*M2[x] : " << ((S[0]-z-1)/M2[x])*M2[x] << ", z : " << z << endl;
	z += ((S[0]-z-1)/M2[x])*M2[x];

	return oinkoinkoinkoink(x, z);
}

long long simulate(int x, int z) {
	return oink(x, z);
}

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