oj.uz

Submission #615121

# Submission time Handle Problem Language Result Execution time Memory
615121 2022-07-31T06:59:30 Z zz(#8674) Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 76924 KB 
#include <bits/stdc++.h>
using namespace std;

int M;

struct seg {
	int sz;
	vector<int> T, L;
	void push(int idx, int s, int e) {
		if(L[idx] != 1) {
			T[idx] = 1LL * T[idx] * L[idx] % M;
			if(s != e) {
				L[idx*2] = 1LL * L[idx*2] * L[idx] % M;
				L[idx*2+1] = 1LL * L[idx*2+1] * L[idx] % M;
			}
			L[idx] = 1;
		}
	}
	void upd(int idx, int s, int e, int l, int r, int v) {
		push(idx, s, e);
		if(r < s || e < l) return;
		if(l <= s && e <= r) {
			L[idx] = v;
			push(idx, s, e);
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, l, r, v);
		upd(idx*2+1, m+1, e, l, r, v);
	}
	void upd(int l, int r, int v) {
		upd(1, 0, sz-1, l, r, v);
	}
	int get(int idx, int s, int e, int p) {
		push(idx, s, e);
		if(p < s || e < p) return 0;
		if(s == e) return T[idx];
		int m = s+e >> 1;
		return get(idx*2, s, m, p) ^ get(idx*2+1, m+1, e, p);
	}
	int get(int p) {
		return get(1, 0, sz-1, p);
	}
	void init(vector<int> &A, int idx, int s, int e) {
		T[idx] = L[idx] = 1;
		if(s == e) {
			T[idx] = A[s];
			return;
		}
		int m = s+e >> 1;
		init(A, idx*2, s, m);
		init(A, idx*2+1, m+1, e);
	}
	void init(vector<int> A) {
		sz = A.size();
		T.resize(4*sz);
		L.resize(4*sz);
		init(A, 1, 0, sz-1);
	}
} S[200009];

vector<int> G[200009], L[200009];
int H[200009], P[22][200009], l, in[200009], ou[200009], ti, dep[200009], ord[200009], md, C[200009];

void dfs(int x, int p, int d) {
	in[x] = ++ti;
	P[0][x] = p;
	dep[x] = d;
	ord[x] = L[d].size();
	md = max(md, d);
	L[d].push_back(x);
	for(auto& it: G[x]) if(it != p) {
		C[x] = it;
		dfs(it, x, d+1);
	}
	ou[x] = ti;
}

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

int lca(int u, int v) {
	if(isup(u, v)) return u;
	if(isup(v, u)) return v;
	for(int i=l; i>=0; i--) if(!isup(P[i][u], v)) u = P[i][u];
	return P[0][u];
}

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

pair<int, int> fnd(int c, int x, int d) {
	int l = 0, r = ord[c];
	while(l <= r) {
		int m = l+r >> 1;
		if(dst(L[dep[c]][m], x) <= d) r = m-1;
		else l = m+1;
	}
	int s = r+1;
	l = ord[c], r = L[dep[c]].size() - 1;
	while(l <= r) {
		int m = l+r >> 1;
		if(dst(L[dep[c]][m], x) <= d) l = m+1;
		else r = m-1;
	}
	int e = l-1;
	return make_pair(s, e);
}

int main() {
	int N; scanf("%d%d", &N, &M);
	for(int i=1; i<N; i++) {
		int u, v; scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1; i<=N; i++) scanf("%d", &H[i]);
	dfs(1, 1, 0);
	for(int i=1; (1<<i)<=N; i++) {
		for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];
		l = i;
	}
	for(int i=0; i<=md; i++) {
		vector<int> A;
		for(auto& it: L[i]) A.push_back(H[it]);
		S[i].init(A);
	}
	int Q; scanf("%d", &Q);
	for(int i=1; i<=Q; i++) {
		int t, x; scanf("%d%d", &t, &x);
		if(t == 1) {
			int d, w; scanf("%d%d", &d, &w);
			int c = x;
			for(int i=0; i<=d; i++) {
				int l = 0, r = ord[c];
				int s, e; tie(s, e) = fnd(c, x, d);
				//printf("d: %d, [%d, %d]\n", dep[c], s, e);
				//S[dep[c]].upd(s, e, w);
				for(int j=s; j<=e; j++) {
					H[L[dep[c]][j]] = 1LL * H[L[dep[c]][j]] * w % M;
				}
				if(!C[c]) break;
				c = C[c];
			}
			c = x;
			for(int i=1; i<=d; i++) {
				if(P[0][c] == c) break;
				c = P[0][c];
				int s, e; tie(s, e) = fnd(c, x, d);
				//printf("d: %d, [%d, %d]\n", dep[c], s, e);
				//S[dep[c]].upd(s, e, w);
				for(int j=s; j<=e; j++) {
					H[L[dep[c]][j]] = 1LL * H[L[dep[c]][j]] * w % M;
				}
			}
		}
		if(t == 2) {
			//printf("%d\n", S[dep[x]].get(ord[x]));
			printf("%d\n", H[x]);
		}
	}
	return 0;
}

Compilation message

sprinkler.cpp: In member function 'void seg::upd(int, int, int, int, int, int)':
sprinkler.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int m = s+e >> 1;
      |           ~^~
sprinkler.cpp: In member function 'int seg::get(int, int, int, int)':
sprinkler.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int m = s+e >> 1;
      |           ~^~
sprinkler.cpp: In member function 'void seg::init(std::vector<int>&, int, int, int)':
sprinkler.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = s+e >> 1;
      |           ~^~
sprinkler.cpp: In function 'std::pair<int, int> fnd(int, int, int)':
sprinkler.cpp:97:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |   int m = l+r >> 1;
      |           ~^~
sprinkler.cpp:104:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |   int m = l+r >> 1;
      |           ~^~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:137:9: warning: unused variable 'l' [-Wunused-variable]
  137 |     int l = 0, r = ord[c];
      |         ^
sprinkler.cpp:137:16: warning: unused variable 'r' [-Wunused-variable]
  137 |     int l = 0, r = ord[c];
      |                ^
sprinkler.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  int N; scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:119:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  for(int i=1; i<=N; i++) scanf("%d", &H[i]);
      |                          ~~~~~^~~~~~~~~~~~~
sprinkler.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  int Q; scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
sprinkler.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   int t, x; scanf("%d%d", &t, &x);
      |             ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:134:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |    int d, w; scanf("%d%d", &d, &w);
      |              ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 11 ms 20620 KB Output is correct
3 Correct 11 ms 20672 KB Output is correct
4 Correct 14 ms 20920 KB Output is correct
5 Incorrect 18 ms 20852 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 1759 ms 58336 KB Output is correct
3 Execution timed out 4103 ms 54192 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 1759 ms 58336 KB Output is correct
3 Execution timed out 4103 ms 54192 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20692 KB Output is correct
2 Correct 1193 ms 76924 KB Output is correct
3 Execution timed out 4034 ms 71876 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 20692 KB Output is correct
2 Correct 3243 ms 71360 KB Output is correct
3 Execution timed out 4054 ms 66424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 11 ms 20620 KB Output is correct
3 Correct 11 ms 20672 KB Output is correct
4 Correct 14 ms 20920 KB Output is correct
5 Incorrect 18 ms 20852 KB Output isn't correct
6 Halted 0 ms 0 KB -