| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 615187 |
2022-07-31T07:28:29 Z |
zz(#8674) |
Sprinkler (JOI22_sprinkler) |
C++17 |
|
4000 ms |
82560 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], dp[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);
dp[x] = d;
if(L[d+1].size()) C[x] = L[d+1].back();
for(auto& it: G[x]) if(it != p) {
dfs(it, x, d+1);
if(dp[x] < dp[it]) {
dp[x] = dp[it];
C[x] = it;
}
}
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 s = ord[c] + 1, e = ord[c];
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, s = m;
else l = m+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, e = m;
else r = m-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 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(dep[c] == md) break;
if(C[c]) c = C[c];
else c = L[dep[c] + 1][0];
}
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++) {
if(dst(L[dep[c]][j], x) > d) continue;
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:103:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int m = l+r >> 1;
| ~^~
sprinkler.cpp:109:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int m = l+r >> 1;
| ~^~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | int N; scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | int u, v; scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:123:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | for(int i=1; i<=N; i++) scanf("%d", &H[i]);
| ~~~~~^~~~~~~~~~~~~
sprinkler.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | int Q; scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
sprinkler.cpp:136:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | int t, x; scanf("%d%d", &t, &x);
| ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:138:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | int d, w; scanf("%d%d", &d, &w);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
11 ms |
20648 KB |
Output is correct |
| 3 |
Correct |
10 ms |
20704 KB |
Output is correct |
| 4 |
Correct |
13 ms |
20948 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
20820 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
1894 ms |
57668 KB |
Output is correct |
| 3 |
Execution timed out |
4054 ms |
54652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
1894 ms |
57668 KB |
Output is correct |
| 3 |
Execution timed out |
4054 ms |
54652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
1466 ms |
82560 KB |
Output is correct |
| 3 |
Execution timed out |
4064 ms |
75008 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
3371 ms |
77104 KB |
Output is correct |
| 3 |
Execution timed out |
4078 ms |
68764 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
11 ms |
20648 KB |
Output is correct |
| 3 |
Correct |
10 ms |
20704 KB |
Output is correct |
| 4 |
Correct |
13 ms |
20948 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
20820 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
