Submission #1082332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082332		HappyCapybara	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	81 ms	32580 KiB

dungeons

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

#define ll long long

int inf = pow(10, 8);

int n;
vector<int> s, p, w, l;
vector<vector<pair<int,int>>> a, b;

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
	n = N;
	s = S;
	p = P;
	w = W;
	l = L;
	a.resize(n, vector<pair<int,int>>(30));
	b.resize(n, vector<pair<int,int>>(30));
	for (int i=0; i<30; i++){
		for (int j=0; j<n; j++){
			if (i == 0){
				a[j][i] = {l[j], p[j]};
				b[j][i] = {w[j], s[j]};
			}
			else {
				if (a[j][i-1].first == n){
					a[j][i].first = n;
					a[j][i].second = a[j][i-1].second;
				}
				else {
					a[j][i].first = a[a[j][i-1].first][i-1].first;
					a[j][i].second = min(inf, a[j][i-1].second + a[a[j][i-1].first][i-1].second);
				}

				if (b[j][i-1].first == n){
					b[j][i].first = n;
					b[j][i].second = b[j][i-1].second;
				}
				else {
					b[j][i].first = b[b[j][i-1].first][i-1].first;
					b[j][i].second = min(inf, b[j][i-1].second + b[b[j][i-1].first][i-1].second);
				}
			}
		}
	}
    /*for (int i=0; i<n; i++){
        for (int j=0; j<4; j++){
            cout << a[i][j].first << " " << a[i][j].second << " " << b[i][j].first << " " << b[i][j].second << "\n";
        }
    }*/
	return;
}

ll simulate(int x, int z){
	ll y = z;
	while (y < s[0] && x != n){
		int i = 0;
		while (y+a[x][i+1].second < s[0]) i++;
        y += a[x][i].second;
		x = a[x][i].first;
        //cout << x << " " << y << "\n";
	}
    //cout << "a\n";
	while (x != n){
        int i = 0;
		while (b[x][i+1].first != n) i++;
        y += b[x][i].second;
		x = b[x][i].first;
        //cout << x << " " << y << "\n";
	}
	return y;
}

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