제출 #565667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565667		PiejanVDC	던전 (IOI21_dungeons)	C++17	13 / 100	1424 ms	286464 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;

vector<int> S_;

struct S {
	vector<long long>v = {LLONG_MIN,LLONG_MIN,LLONG_MIN,LLONG_MIN,LLONG_MIN};
	int nxt;
};

vector<vector<S>>win_jump;
vector<vector<long long>>win_score;
vector<vector<S>>lose_jump;
vector<vector<long long>>lose_score;

map<int,int>pos;

int n;

void init(int N, vector<int>s, vector<int>p, vector<int>w, vector<int>l) {
	n = N;
	set<int>st;
	
	for(auto z : s)
		st.insert(z);
	
	auto it = st.begin();
	for(int i = 0 ; i < min(5, (int)st.size()) ; i++, it++)
		S_.push_back(*it), pos[*it] = i;
	
	while((int)S_.size() < 5)
		S_.push_back(-1);

	win_jump.resize(n+5);
	win_score.resize(n+5);
	lose_jump.resize(n+5);
	lose_score.resize(n+5);

	for(int i = 0 ; i <= n ; i++)
		win_jump[i].resize(32), win_score[i].resize(32), lose_jump[i].resize(32), lose_score[i].resize(32);

	w.push_back(n), l.push_back(n), s.push_back(0), p.push_back(0);

	for(int i = 0 ; i <= n ; i++) {
		win_jump[i][0].v[pos[s[i]]] = s[i];
		win_jump[i][0].nxt = w[i];
		win_score[i][0] = s[i];
		lose_jump[i][0].v[pos[s[i]]] = s[i];
		lose_jump[i][0].nxt = l[i];
		lose_score[i][0] = p[i];
	}

	for(int j = 1 ; j <= 30 ; j++) {
		for(int i = 0 ; i <= n ; i++) {
			
			win_score[i][j] = win_score[i][j-1] + win_score[win_jump[i][j-1].nxt][j-1];
			lose_score[i][j] = lose_score[i][j-1] + lose_score[lose_jump[i][j-1].nxt][j-1];
			win_jump[i][j].nxt = win_jump[win_jump[i][j-1].nxt][j-1].nxt;
			lose_jump[i][j].nxt = lose_jump[lose_jump[i][j-1].nxt][j-1].nxt;
			
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(win_jump[win_jump[i][j-1].nxt][j-1].v[ii] != LLONG_MIN) {
					win_jump[i][j].v[ii] = win_jump[win_jump[i][j-1].nxt][j-1].v[ii] - win_score[i][j-1];
				} else if(win_jump[i][j-1].v[ii] != LLONG_MIN) {
					win_jump[i][j].v[ii] = win_jump[i][j-1].v[ii];
				}
				if(lose_jump[lose_jump[i][j-1].nxt][j-1].v[ii] != LLONG_MIN) {
					lose_jump[i][j].v[ii] = lose_jump[lose_jump[i][j-1].nxt][j-1].v[ii] - lose_score[i][j-1];
				} else if(lose_jump[i][j-1].v[ii] != LLONG_MIN) {
					lose_jump[i][j].v[ii] = lose_jump[i][j-1].v[ii];
				}
				//cout << i << " " << j << " " << ii << " " << win_jump[i][j].v[ii] << " " << lose_jump[i][j].v[ii] << "\n";
			}
		}
	}
}

long long simulate(int x, int z) {
	long long s = z;
	while(x != n) {
		
		for(int j = 30 ; j >= 0 ; j--) {
			bool ok = lose_jump[x][j].nxt != n;
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(lose_jump[x][j].v[ii] != LLONG_MIN && lose_jump[x][j].v[ii]-s <= 0)
					ok = 0;
			}
			if(ok)
				s += lose_score[x][j], x = lose_jump[x][j].nxt;
		}
		
		for(int j = 30 ; j >= 0 ; j--) {
			bool ok = win_jump[x][j].nxt != n;
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(win_jump[x][j].v[ii] != LLONG_MIN && win_jump[x][j].v[ii]-s > 0)
					ok = 0;
			}
			if(ok)
				s += win_score[x][j], x = win_jump[x][j].nxt;
		}
		
		if(x != n) {
			bool ok = 1;
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(win_jump[x][0].v[ii] != LLONG_MIN && win_jump[x][0].v[ii]-s > 0)
					ok = 0;
			}
			if(ok)
				s += win_score[x][0], x = win_jump[x][0].nxt;
			else
				s += lose_score[x][0], x = lose_jump[x][0].nxt;
		}

	}

	assert(x == n);
	return s;
}
/*
#include <vector>
#include <cassert>
#include <cstdio>

static int q;
static std::vector<int> s, p, z;
static std::vector<int> w, l, x;
static std::vector<long long> answer;

int main() {
	assert(scanf("%d %d", &n, &q) == 2);
	s.resize(n);
	p.resize(n);
	w.resize(n);
	l.resize(n);
    x.resize(q);
    z.resize(q);
    answer.resize(q);

	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &s[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &p[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &w[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &l[i]) == 1);
	}


    init(n, s, p, w, l);

    for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &z[i]) == 2);
		answer[i] = simulate(x[i], z[i]);
    }

    for (int i = 0; i < q; i++) {
        printf("%lld\n", answer[i]);
    }
    return 0;
}
*/

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