Submission #1195947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195947		belgianbot	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	1 ms	1864 KiB

dungeons

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

const int MAX_N = 50001;
vector<bool> processed(MAX_N,false), is_processing(MAX_N, false), is_cycle(MAX_N, false);
vector<long long> cycle(MAX_N), win(MAX_N), distCycle(MAX_N);
vector<int> s,p,w,l, toCycle(MAX_N);
stack<int> q;
int n;

int proc(int i) {
	if (i == n) return n;
	if (is_processing[i]) {
		while(!q.empty()) {
			int x = q.top(); q.pop();
			is_processing[x] = false;
			is_cycle[x] = true;
			distCycle[x] = 0;
			if (x == i) break;
		}
		return i;
	}
	if (processed[i]) return toCycle[i];
	is_processing[i] = true;
	processed[i] =true;
	q.push(i);
	return proc(l[i]);
}
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	s = ss; p = pp; w = ww; l = ll; n = nn;
	for (int i = 0; i < n; i++) {
		if (!processed[i]) {
			int cy = proc(i);
			long long sz = distCycle[cy];
			while (!q.empty()) {
				int x = q.top(); q.pop();
				sz += p[x];
				distCycle[x] = sz;
				toCycle[x] = cy;
				is_processing[x] = false;
			}
		}
	}
	processed.clear();
	processed.resize(MAX_N,false);
	for (int i = 0; i < n; i++) {
		if (processed[i] || !is_cycle[i]) continue;
		int pos = i;
		long long sz = 0;
		while (!processed[pos]) {
			processed[pos] = true;
			q.push(pos);
			sz += p[pos];
			pos = l[pos];
		}
		while (!q.empty()) {
			int x = q.top(); q.pop();
			cycle[x] = sz;
		}
	}
	win[n] = 0;
	for (int i = n-1; i >= 0; i--) {
		win[i] = win[w[i]] + s[i];
	}
	return;
}

long long simulate(int x, int z) {
	long long lim = s[x];
	long long st = z;
	int pos = x;
	if (st >= lim) return st+ win[pos];
	
	if (st + distCycle[pos] < lim) {
		while (!is_cycle[pos] && st < lim && pos != n) {
			st += (long long)(p[pos]);
			pos = l[pos];
		}
		if (pos == n) return st;
		if (st >= lim) return st + win[pos];
	}
	st += distCycle[pos];
	pos = toCycle[pos];
	st += ((lim - st) / cycle[pos]) * cycle[pos];
	
	while (st < lim && pos != n) {
		st += (long long)(p[pos]);
		pos = l[pos];
	}
	if (pos == n) return st;
	return st + win[pos];
}

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