제출 #524731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524731		LucaDantas	던전 (IOI21_dungeons)	C++17	37 / 100	7061 ms	397104 KiB

dungeons

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

constexpr int maxn = 4e5+10, logn = 25;
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];

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

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

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

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

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

		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;
	for(int lg = 0; lg < logn; lg++)
		if(x != n) graph[lg].go(x, val);
	assert(x == n);
	return val;
}

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