제출 #1266050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266050		nicolo_010	던전 (IOI21_dungeons)	C++20	0 / 100	102 ms	63800 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define cerr if(0) cerr

v<ll> S, P, L, W;
v<ll> afterwin;
v<v<v<ll>>> lift;

void init(int n, v<int> s, v<int> p, v<int> w, v<int> l) {
	s.push_back(s[0]);
	p.push_back(0);
	l.push_back(n);
	w.push_back(n);
	S.resize(n+1);
	P.resize(n+1);
	L.resize(n+1);
	W.resize(n+1);
	for (int i=0; i<=n; i++) {
		S[i] = s[i];
		P[i] = p[i];
		W[i] = w[i];
		L[i] = l[i];
	}
	afterwin.resize(n+1);
	afterwin[n] = 0;
	for (int i=n-1; i >= 0; i--) {
		afterwin[i] = 1+afterwin[w[i]];
	}
	//cerr << "? " << endl;
	lift.assign(n+1, v<v<ll>>(21, v<ll>(2)));
	for (int i=0; i<=n; i++) {
		lift[i][0][0] = l[i];
		lift[i][0][1] = p[i];
	}
	//cerr << "? " << endl;	
	for (int j=1; j<21; j++) {
		for (int i=0; i<=n; i++) {
			lift[i][j][0] = lift[lift[i][j-1][0]][j-1][0];
			lift[i][j][1] = lift[lift[i][j-1][0]][j-1][1] + lift[i][j-1][1];
		}
	}
}

ll simulate(int x, int z) {
	ll sum = z;
	int aux = x;
	int n = S.size();
	cerr << S[x] << endl;
	for (int i=20; i>=0; i--) {
		if (x == n) continue;
		if (sum+lift[x][i][1] < S[x]) {
			sum += lift[x][i][1];
			x = lift[x][i][0];
		}
	}
	if (sum < S[x] && x != n) {
		sum += P[x];
		x = L[x];
	}
	cerr << x << " "<< sum << endl;
	return sum + afterwin[x]*S[x];
}

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