oj.uz

Submission #551729

# Submission time Handle Problem Language Result Execution time Memory
551729 2022-04-21T11:44:51 Z nonsensenonsense1 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 63332 KB 
#include <cstdio>
#include <vector>

int md;
inline int mul(int a, int b) {
	return (long long)a * b % md;
}

const int N = 200000;
const int LG = 18;
const int K = 500;
std::vector<int> g[N], list[N], t[N];
int q, n, dep[N], pr[LG][N], in[N], out[N], pos[N], h[N];

void dfs(int v) {
	static int dt = 0;
	in[v] = dt++;
	pos[v] = list[dep[v]].size();
	list[dep[v]].push_back(v);
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr[0][v]) {
		pr[0][g[v][i]] = v;
		dep[g[v][i]] = dep[v] + 1;
		dfs(g[v][i]);
	}
	out[v] = dt;
}

bool par(int u, int v) {
	return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v) {
	if (par(u, v)) return u;
	for (int i = LG - 1; i >= 0; --i) if (!par(pr[i][u], v)) u = pr[i][u];
	return pr[0][u];
}

int f(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void update(std::vector<int> &t, int l, int r, int x) {
	for (l += t.size() >> 1, r += t.size() >> 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			t[l] = mul(t[l], x);
			++l;
		}
		if (r & 1) {
			--r;
			t[r] = mul(t[r], x);
		}
	}
}

int get(std::vector<int> &t, int i) {
	int res = 1;
	for (i += t.size() >> 1; i > 0; i >>= 1) res = mul(res, t[i]);
	return res;
}

int main() {
	scanf("%d%d", &n, &md);
	for (int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}
	dfs(0);
	for (int j = 1; j < LG; ++j) for (int i = 0; i < n; ++i) pr[j][i] = pr[j - 1][pr[j - 1][i]];
	for (int i = 0; i < n; ++i) scanf("%d", h + i);
	for (int i = 0; i < n; ++i) t[i].resize(list[i].size() << 1, 1);
	scanf("%d", &q);
	while (q--) {
		int type, v;
		scanf("%d%d", &type, &v);
		--v;
		if (type == 1) {
			int dist, x;
			scanf("%d%d", &dist, &x);
			for (int i = dep[v] + dist; i >= dep[v] - dist; --i) {
				int l, r;
				for (l = 0; l < (int)list[i].size() && f(list[i][l], v) > dist; ++l);
				for (r = (int)list[i].size(); r > 0 && f(list[i][r - 1], v) > dist; --r);
				update(t[i], l, r, x);
			}
		} else printf("%d\n", mul(h[v], get(t[dep[v]], pos[v])));
	}
	return 0;
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d", &n, &md);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:71:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  for (int i = 0; i < n; ++i) scanf("%d", h + i);
      |                              ~~~~~^~~~~~~~~~~~~
sprinkler.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
sprinkler.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d", &type, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d%d", &dist, &x);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14496 KB Output is correct
2 Correct 8 ms 14496 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 13 ms 14600 KB Output is correct
5 Correct 33 ms 14548 KB Output is correct
6 Correct 26 ms 14676 KB Output is correct
7 Correct 21 ms 14576 KB Output is correct
8 Correct 11 ms 14676 KB Output is correct
9 Correct 8 ms 14512 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14444 KB Output is correct
13 Correct 8 ms 14516 KB Output is correct
14 Correct 8 ms 14524 KB Output is correct
15 Correct 9 ms 14508 KB Output is correct
16 Correct 8 ms 14428 KB Output is correct
17 Correct 8 ms 14528 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 8 ms 14396 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 8 ms 14420 KB Output is correct
26 Correct 8 ms 14420 KB Output is correct
27 Correct 8 ms 14420 KB Output is correct
28 Correct 8 ms 14512 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 4085 ms 42212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 4085 ms 42212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 3491 ms 63332 KB Output is correct
3 Execution timed out 4085 ms 60224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14496 KB Output is correct
2 Correct 8 ms 14496 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 13 ms 14600 KB Output is correct
5 Correct 33 ms 14548 KB Output is correct
6 Correct 26 ms 14676 KB Output is correct
7 Correct 21 ms 14576 KB Output is correct
8 Correct 11 ms 14676 KB Output is correct
9 Correct 8 ms 14512 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 8 ms 14444 KB Output is correct
13 Correct 8 ms 14516 KB Output is correct
14 Correct 8 ms 14524 KB Output is correct
15 Correct 9 ms 14508 KB Output is correct
16 Correct 8 ms 14428 KB Output is correct
17 Correct 8 ms 14528 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 8 ms 14396 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 8 ms 14420 KB Output is correct
26 Correct 8 ms 14420 KB Output is correct
27 Correct 8 ms 14420 KB Output is correct
28 Correct 8 ms 14512 KB Output is correct
29 Correct 8 ms 14420 KB Output is correct
30 Execution timed out 4085 ms 42212 KB Time limit exceeded
31 Halted 0 ms 0 KB -