Submission #1082360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082360		HappyCapybara	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	138 ms	55716 KiB

dungeons

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

#define ll long long

int n;
vector<int> s, p, w, l;
vector<vector<pair<int,ll>>> 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;
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);
	a.resize(n+1, vector<pair<int,ll>>(30));
	b.resize(n+1, vector<pair<int,ll>>(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 {
				a[j][i].first = a[a[j][i-1].first][i-1].first;
				a[j][i].second = a[j][i-1].second + a[a[j][i-1].first][i-1].second;
				b[j][i].first = b[b[j][i-1].first][i-1].first;
				b[j][i].second = 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 (i<29 && 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 (i<29 && 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: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11