oj.uz

Submission #580871

# Submission time Handle Problem Language Result Execution time Memory
580871 2022-06-22T03:47:15 Z JustInCase Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 61576 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 45652 KB Output is correct
2 Correct 21 ms 45728 KB Output is correct
3 Correct 23 ms 45708 KB Output is correct
4 Correct 25 ms 45772 KB Output is correct
5 Correct 28 ms 45792 KB Output is correct
6 Correct 26 ms 45748 KB Output is correct
7 Correct 25 ms 45772 KB Output is correct
8 Correct 25 ms 45780 KB Output is correct
9 Correct 22 ms 45636 KB Output is correct
10 Correct 25 ms 45728 KB Output is correct
11 Correct 24 ms 45712 KB Output is correct
12 Correct 21 ms 45724 KB Output is correct
13 Correct 23 ms 45744 KB Output is correct
14 Correct 24 ms 45764 KB Output is correct
15 Correct 23 ms 45644 KB Output is correct
16 Correct 23 ms 45644 KB Output is correct
17 Correct 24 ms 45644 KB Output is correct
18 Correct 23 ms 45900 KB Output is correct
19 Correct 22 ms 45644 KB Output is correct
20 Correct 23 ms 45728 KB Output is correct
21 Correct 22 ms 45728 KB Output is correct
22 Correct 23 ms 45652 KB Output is correct
23 Correct 23 ms 45720 KB Output is correct
24 Correct 22 ms 45652 KB Output is correct
25 Correct 23 ms 45728 KB Output is correct
26 Correct 24 ms 45716 KB Output is correct
27 Correct 23 ms 45652 KB Output is correct
28 Correct 24 ms 45652 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 45700 KB Output is correct
2 Execution timed out 4066 ms 53936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 45700 KB Output is correct
2 Execution timed out 4066 ms 53936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45652 KB Output is correct
2 Execution timed out 4067 ms 58596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 45652 KB Output is correct
2 Execution timed out 4061 ms 61576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 45652 KB Output is correct
2 Correct 21 ms 45728 KB Output is correct
3 Correct 23 ms 45708 KB Output is correct
4 Correct 25 ms 45772 KB Output is correct
5 Correct 28 ms 45792 KB Output is correct
6 Correct 26 ms 45748 KB Output is correct
7 Correct 25 ms 45772 KB Output is correct
8 Correct 25 ms 45780 KB Output is correct
9 Correct 22 ms 45636 KB Output is correct
10 Correct 25 ms 45728 KB Output is correct
11 Correct 24 ms 45712 KB Output is correct
12 Correct 21 ms 45724 KB Output is correct
13 Correct 23 ms 45744 KB Output is correct
14 Correct 24 ms 45764 KB Output is correct
15 Correct 23 ms 45644 KB Output is correct
16 Correct 23 ms 45644 KB Output is correct
17 Correct 24 ms 45644 KB Output is correct
18 Correct 23 ms 45900 KB Output is correct
19 Correct 22 ms 45644 KB Output is correct
20 Correct 23 ms 45728 KB Output is correct
21 Correct 22 ms 45728 KB Output is correct
22 Correct 23 ms 45652 KB Output is correct
23 Correct 23 ms 45720 KB Output is correct
24 Correct 22 ms 45652 KB Output is correct
25 Correct 23 ms 45728 KB Output is correct
26 Correct 24 ms 45716 KB Output is correct
27 Correct 23 ms 45652 KB Output is correct
28 Correct 24 ms 45652 KB Output is correct
29 Correct 23 ms 45700 KB Output is correct
30 Execution timed out 4066 ms 53936 KB Time limit exceeded
31 Halted 0 ms 0 KB -