Submission #526020

#TimeUsernameProblemLanguageResultExecution timeMemory
526020LucaDantasDungeons Game (IOI21_dungeons)C++17
Compilation error
0 ms0 KiB
// Subtask 2
#include "dungeons.h"
#include <vector>
#include <cstring>

constexpr int maxn = 4e5+10, logn = 25;
constexpr long long inf = 1e15L;

struct FunctionalGraph {
	int n;
	int p[maxn], f[maxn];
	long long s[maxn];
	int tp[maxn];

	void add_edge(int i, int x, int v) { f[i] = x, p[i] = v; }
	void set_s(int i, long long st) { s[i] = st; tp[i] = st != inf; }

	bool in_cycle[maxn];
	int mark[maxn], prox_bom[maxn];
	long long dist_bom[maxn];

	void dfs(int u) {
		mark[u] = 1;

		if(mark[f[u]] == 1) {
			int fim = u; u = f[u]; in_cycle[fim] = 1;
			while(u != fim) in_cycle[u] = 1, u = f[u];
		}
		else if(!mark[f[u]]) dfs(f[u]);

		mark[u] = 2;
	}

	void dfs2(int u) {
		mark[u] = 1;
		if(!mark[f[u]]) dfs2(f[u]);
		dist_bom[u] = tp[u] ? 0 : dist_bom[f[u]] + p[u];
		prox_bom[u] = tp[u] ? u : prox_bom[f[u]];
	}

	void build(int _n) {
		f[n] = n;
		s[n] = 0;
		p[n] = 0;
		tp[n] = 1;

		for(int i = 0; i <= n; i++)
			if(!mark[i]) dfs(i);
		
		memset(mark, 0, sizeof mark);
		for(int i = 0; i <= n; i++)
			if(!mark[i] && in_cycle[i] && tp[i]) {
				prox_bom[i] = i, dist_bom[i] = 0;
				dfs2(i);
			}

		for(int i = 0; i <= n; i++)
			if(!mark[i]) dfs2(i);
	}

	void go(int& x, long long& val) {
		val += dist_bom[x];
		x = prox_bom[x];

		if(val >= s[x]) return;

		val += p[x];
		x = f[x];

		go(x, val);
	}
} graph[logn];

int n;

void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	n = N;
	for(int i = 0; i < n; i++)
		s[i] = S[i];
	for(int i = 0; i < n; i++)
		p[i] = P[i];
	for(int i = 0; i < n; i++)
		w[i] = W[i];
	for(int i = 0; i < n; i++)
		l[i] = L[i];

	for(int lg = 0; lg < logn; lg++) {
		int lim = 1<<lg;

		for(int i = 0; i < n; i++) {
			if(s[i] <= lim) {
				graph[lg].add_edge(i, w[i], s[i]);
				graph[lg].set_s(i, inf);
			} else {
				graph[lg].add_edge(i, l[i], p[i]);
				graph[lg].set_s(i, s[i]);
			}
		}

		graph[lg].build(n);
	}

	return;
}

long long simulate(int x, int z) {
	long long val = z;
	for(int lg = 0; lg < logn; lg++)
		if(x != n) graph[lg].go(x, val);
	return val;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:79:10: error: 'S' was not declared in this scope
   79 |   s[i] = S[i];
      |          ^
dungeons.cpp:81:10: error: 'P' was not declared in this scope
   81 |   p[i] = P[i];
      |          ^
dungeons.cpp:83:10: error: 'W' was not declared in this scope
   83 |   w[i] = W[i];
      |          ^
dungeons.cpp:85:10: error: 'L' was not declared in this scope
   85 |   l[i] = L[i];
      |          ^