Submission #524722

#	Time	Username	Problem	Language	Result	Execution time	Memory
524722		LucaDantas	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7 ms	16376 KiB

dungeons

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

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

struct FunctionalGraph {
	int n;
	int p[maxn], f[maxn]; // s[i] == força necessaria para matar i, p[i] == peso da aresta saindo de i, f[i] == aresta saindo de i
	long long s[maxn];
	int tp[maxn]; // se tá vivo ou se tá morto, definido junto com o s[i]

	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];

	// int prox_cycle[maxn];
	// long long dist_cycle[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 dfs_cycle(int u, int fim) { // tenho q comecar em f[bom], com bom estando no ciclo
		mark[u] = 1;
		if(u != fim) dfs_cycle(f[u], fim);
		dist_bom[u] = tp[u] ? 0 : dist_bom[f[u]] + p[u];
		prox_bom[u] = tp[u] ? u : prox_bom[f[u]];
	}

	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, int debugar = 0) { // n é a quantidade de vertices desse grafo, n é sempre igual ao n geral, não é um grafo compresso
		n = _n;

		f[n] = n;
		s[n] = 0;
		p[n] = 0;
		tp[n] = 1;
		in_cycle[n] = 1;

		memset(prox_bom, -1, sizeof prox_bom);

		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]) dfs_cycle(f[i], i);

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

		if(debugar) {
			for(int i = 0; i <= n; i++) {
				printf("%d == \n", i);
				printf("%lld %d %d\n", s[i], p[i], f[i]);
				
				// printf("(%d %lld) ", prox_bom[i], dist_bom[i]);

				puts("\n");
			}
		}
	}

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

		// printf("%d %lld\n\n", x, val);

		if(val >= s[x]) return; // na subtask s[i] == p[i] isso só vai ser falso uma vez então essa recursão é O(1)

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

		// printf("%d %lld\n", x, val);

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

int s[maxn], p[maxn], w[maxn], l[maxn], 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); // já ta morto
			} 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;
	// printf("%d %lld\n", x, val);
	for(int lg = 0; lg < logn; lg++) {
		graph[lg].go(x, val);
		// printf("%d %lld\n", x, val);
	}
	// puts("");
	return val;
	// return 0;
}

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