| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1030980 |
2024-07-22T13:12:40 Z |
pera |
Sprinkler (JOI22_sprinkler) |
C++17 |
|
4000 ms |
96496 KB |
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 1;
int n , M , Q , o = 0;
vector<int> t(4 * N) , lz(4 * N) , H(N) , in(N) , out(N) , d(N) , id(N) , up(N) , order = {0};
vector<vector<int>> g(N) , E(N) , D(N);
void dfs(int u , int p = 0){
order.push_back(u);
up[u] = p;
in[u] = ++o;
d[u] = d[p] + 1;
E[d[u]].push_back(in[u]);
if(u != 1){
g[u].erase(find(g[u].begin() , g[u].end() , p));
}
for(int x = 0;x < (int)g[u].size();x ++){
dfs(g[u][x] , u);
}
out[u] = o;
}
void build(int u , int l , int r){
t[u] = lz[u] = 1;
if(l != r){
int m = (l + r) / 2;
build(u * 2 , l , m);
build(u * 2 + 1 , m + 1 , r);
}
}
void push(int u){
t[u * 2] = t[u * 2] * lz[u] % M;
t[u * 2 + 1] = t[u * 2 + 1] * lz[u] % M;
lz[u * 2] = lz[u * 2] * lz[u] % M;
lz[u * 2 + 1] = lz[u * 2 + 1] * lz[u] % M;
lz[u] = 1;
}
void upd(int u , int l , int r , int L , int R , int w){
if(l > r || r < L || l > R){
return ;
}
if(L <= l && r <= R){
int bf = t[u];
t[u] = t[u] * w % M;
lz[u] = lz[u] * w % M;
return;
}
int m = (l + r) / 2;
push(u);
upd(u * 2 , l , m , L , R , w);
upd(u * 2 + 1 , m + 1 , r , L , R , w);
}
int get(int u , int l , int r , int pos){
if(l == r){
return t[u];
}
int m = (l + r) / 2;
push(u);
if(pos <= m){
return get(u * 2 , l , m , pos);
}
return get(u * 2 + 1 , m + 1 , r , pos);
}
int GET(int u){
return get(1 , 1 , n , id[u]);
}
void UPD(int u , int x , int W){
for(int depth = d[u];depth <= min(d[u] + x , n);depth ++){
//[in[u] , out[u]] -> id[first] , id[last];
int L = -1 , R = -1;
for(int bit = 20;bit >= 0;bit --){
if(L + (1 << bit) < (int)E[depth].size()){
if(E[depth][L + (1 << bit)] < in[u]){
L += (1 << bit);
}
}
if(R + (1 << bit) < (int)E[depth].size()){
if(E[depth][R + (1 << bit)] <= out[u]){
R += (1 << bit);
}
}
}
++L;
if(0 <= min(L , R) && max(L , R) < (int)E[depth].size() && in[u] <= min(E[depth][L] , E[depth][R]) && max(E[depth][L] , E[depth][R]) <= out[u] && L <= R){
upd(1 , 1 , n , D[depth][L] , D[depth][R] , W);
}
}
if(u != 1){
int cnt = x , v = u , lst;
while(v != 1 && cnt > 0){
H[up[v]] = H[up[v]] * W % M;
lst = v;
v = up[v];
--cnt;
for(int depth = d[v] + 1;depth <= d[v] + cnt + 1;depth ++){
int posL = -1 , posR;
for(int bit = 20;bit >= 0;bit --){
if(posL + (1 << bit) < (int)E[depth].size()){
if(E[depth][posL + (1 << bit)] < in[lst]){
posL += (1 << bit);
}
}
if(posR + (1 << bit) < (int)E[depth].size()){
if(E[depth][posR + (1 << bit)] <= out[lst]){
posR += (1 << bit);
}
}
}
++posR;
if(posL >= 0){
upd(1 , 1 , n , D[depth][0] , D[depth][posL] , W);
}
if(posR < (int)E[depth].size()){
upd(1 , 1 , n , D[depth][posR] , D[depth].back() , W);
}
}
}
}
}
main(){
cin >> n >> M;
for(int i = 1;i < n;i ++){
int u , v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
build(1 , 1 , n);
o = 0;
for(int a = 1;a <= n;a ++){
for(int x : E[a]){
id[order[x]] = ++o;
D[a].push_back(id[order[x]]);
}
}
for(int i = 1;i <= n;i ++){
cin >> H[i];
}
cin >> Q;
while(Q--){
int e;
cin >> e;
if(e == 1){
int x , d , W;
cin >> x >> d >> W;
UPD(x , d , W);
}else{
int x;
cin >> x;
cout << H[x] * GET(x) % M << endl;
}
}
}
Compilation message
sprinkler.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
sprinkler.cpp:42:11: warning: unused variable 'bf' [-Wunused-variable]
42 | int bf = t[u];
| ^~
sprinkler.cpp: At global scope:
sprinkler.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
119 | main(){
| ^~~~
sprinkler.cpp: In function 'void UPD(long long int, long long int, long long int)':
sprinkler.cpp:102:24: warning: 'posR' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | if(posR + (1 << bit) < (int)E[depth].size()){
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
72276 KB |
Output is correct |
| 2 |
Correct |
26 ms |
72284 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
72252 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
72280 KB |
Output is correct |
| 2 |
Incorrect |
955 ms |
89284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
72280 KB |
Output is correct |
| 2 |
Incorrect |
955 ms |
89284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
72276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
72284 KB |
Output is correct |
| 2 |
Execution timed out |
4103 ms |
96496 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
72276 KB |
Output is correct |
| 2 |
Correct |
26 ms |
72284 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
72252 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
