Submission #580871

#	Time	Username	Problem	Language	Result	Execution time	Memory
580871		JustInCase	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	4067 ms	61576 KiB

sprinkler

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>

#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));

const int32_t MAX_N = 2e5;
const int32_t LOG_MAX_N = 19;
const int32_t BUCKET = 600;

struct Vertex {
	int32_t milletH;
	int32_t dep, inTime, outTime;
	std::vector< Vertex* > adj;
	Vertex *ancs[LOG_MAX_N + 5];

	Vertex() {
		for(int32_t i = 0; i <= LOG_MAX_N; i++) {
			ancs[i] = nullptr;
		}
	}
};

Vertex g[MAX_N + 5];

void precompute_parents(Vertex *v, int32_t dep, Vertex *parent, int32_t &t) {
	v->dep = dep;
	v->ancs[0] = parent;
	v->inTime = t++;

	for(auto &u : v->adj) {
		if(u != parent) {
			precompute_parents(u, dep + 1, v, t);
		}
	}

	v->outTime = t++;
}

void precompute_ancestors(int32_t n) {
	for(int32_t j = 1; j <= LOG_MAX_N; j++) {
		for(int32_t i = 1; i <= n; i++) {
			if(g[i].ancs[j - 1] != nullptr) {
				g[i].ancs[j] = g[i].ancs[j - 1]->ancs[j - 1];
			}
		}
	}
}

bool isAnc(Vertex *v, Vertex *u) {
	return (v->inTime <= u->inTime && v->outTime >= u->outTime);
}

Vertex *getLca(Vertex *v, Vertex *u) {
	if(isAnc(v, u)) return v;
	if(isAnc(u, v)) return u;

	for(int32_t i = LOG_MAX_N; i >= 0; i--) {
		if(v->ancs[i] != nullptr && !isAnc(v->ancs[i], u)) {
			v = v->ancs[i];
		}
	}

	return v->ancs[0];
}

int32_t getDistance(Vertex *v, Vertex *u) {
	auto lca = getLca(v, u);
	return v->dep + u->dep - 2 * lca->dep;
}

void update(int32_t n, int32_t l, std::vector< std::tuple< int32_t, int32_t, int32_t > > updates) {
	// TODO
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n, l;
	std::cin >> n >> l;

	for(int32_t i = 0; i < n - 1; i++) {
		int32_t u, v;
		std::cin >> u >> v;

		g[u].adj.push_back(&g[v]);
		g[v].adj.push_back(&g[u]);
	}

	int32_t t = 0;
	precompute_parents(&g[1], 0, nullptr, t);
	precompute_ancestors(n);

	/**
	for(int32_t i = 1; i <= n; i++) {
		for(int32_t j = i; j <= n; j++) {
			std::cout << i << ", " << j << ": " << getDistance(&g[i], &g[j]) << std::endl;
		}
	}

	return 0;
	*/

	for(int32_t i = 1; i <= n; i++) {
		std::cin >> g[i].milletH;
	}

	int32_t q;
	std::cin >> q;

	std::vector< std::tuple< int32_t, int32_t, int32_t > > notUpdated;
	for(int32_t i = 0; i < q; i++) {
		int32_t type;
		std::cin >> type;

		if(type == 1) {
			int32_t x, d, w;
			std::cin >> x >> d >> w;

			notUpdated.push_back(std::make_tuple(x, d, w));
			if((int32_t) notUpdated.size() > BUCKET) {
				update(n, l, notUpdated);
			}
		}
		else {
			int32_t x;
			std::cin >> x;

			int32_t updatedValue = g[x].milletH;
			for(auto &a : notUpdated) {
				int32_t dist = getDistance(&g[x], &g[std::get<0>(a)]);
				if(dist <= std::get<1>(a)) {
					updatedValue = ((int64_t) updatedValue * std::get<2>(a)) % l;
				}
			}

			std::cout << updatedValue << '\n';
		}
	}
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17