| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 615097 |
2022-07-31T06:45:58 Z |
이동현(#8495) |
Sprinkler (JOI22_sprinkler) |
C++17 |
|
4000 ms |
756984 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NS = (int)2e5 + 4;
int n, mod;
vector<int> way[NS], cway[NS];
int dep[NS], sz[NS], megop[NS][44], ind[NS];
int lca[NS][20], cchk[NS], init[NS];
int cpr[NS];
struct Seg{
int n;
vector<int> tr;
Seg(){}
Seg(int n):n(n + 4){
tr.resize(n * 4, 1);
}
void push(int x, int s, int e, int pos, int val){
if(s == e){
tr[x] = (tr[x] * val) % mod;
return;
}
int m = s + e >> 1;
if(pos <= m){
push(x * 2, s, m, pos, val);
}
else{
push(x * 2 + 1, m + 1, e, pos, val);
}
tr[x] = (tr[x * 2] * tr[x * 2 + 1]) % mod;
}
int get(int x, int s, int e, int fs, int fe){
if(fe < s || fs > e || fs > fe) return 1;
if(fs <= s && fe >= e){
return tr[x];
}
int m = s + e >> 1;
return get(x * 2, s, m, fs, fe) * get(x * 2 + 1, m + 1, e, fs, fe) % mod;
}
}tree[NS][44];
void dfslca(int x, int pr){
lca[x][0] = pr;
for(auto&nxt:way[x]){
if(nxt == pr){
continue;
}
dep[nxt] = dep[x] + 1;
dfslca(nxt, x);
}
}
void dfssz(int x, int pr = -1){
sz[x] = 1;
for(auto&nxt:way[x]){
if(nxt == pr || cchk[nxt]){
continue;
}
dfssz(nxt, x);
sz[x] += sz[nxt];
}
}
int getcent(int x, int allsz, int pr = -1){
for(auto&nxt:way[x]){
if(nxt == pr || cchk[nxt]){
continue;
}
if(sz[nxt] * 2 > allsz){
return getcent(nxt, allsz, x);
}
}
return x;
}
int docent(int x){
dfssz(x);
x = getcent(x, sz[x]);
cchk[x] = 1;
for(auto&nxt:way[x]){
if(cchk[nxt]){
continue;
}
int rv = docent(nxt);
ind[rv] = (int)cway[x].size();
cway[x].push_back(rv);
cpr[rv] = x;
}
return x;
}
int getdist(int x, int y){
int xs = x, ys = y;
if(dep[x] < dep[y]){
swap(x, y);
}
for(int i = 19; i >= 0; --i){
if(dep[x] - (1 << i) >= dep[y]){
x = lca[x][i];
}
}
if(x != y){
for(int i = 19; i >= 0; --i){
if(lca[x][i] != lca[y][i]){
x = lca[x][i];
y = lca[y][i];
}
}
x = lca[x][0];
}
return dep[xs] + dep[ys] - 2 * dep[x];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> mod;
for(int i = 1; i < n; ++i){
int x, y; cin >> x >> y;
way[x].push_back(y), way[y].push_back(x);
}
for(int i = 1; i <= n; ++i){
cin >> init[i];
}
dfslca(1, 0);
for(int j = 1; j < 20; ++j){
for(int i = 1; i <= n; ++i){
lca[i][j] = lca[lca[i][j - 1]][j - 1];
}
}
int top = docent(1);
for(int i = 1; i <= n; ++i){
for(int j = 0; j <= 40; ++j){
tree[i][j] = Seg((int)cway[i].size());
megop[i][j] = 1;
}
}
int q; cin >> q;
while(q--){
int t; cin >> t;
if(t == 1){
int x, d, w; cin >> x >> d >> w;
int now = x;
for(int i = 0; i <= d; ++i){
megop[now][i] = (megop[now][i] * w) % mod;
}
while(now != top){
int up = cpr[now];
int dist = getdist(x, up);
if(d >= dist){
for(int i = 0; i <= d - dist; ++i){
tree[up][i].push(1, 0, (int)cway[up].size() - 1, ind[now], w);
}
}
now = up;
}
}
else{
int x; cin >> x;
int ans = init[x];
int now = x;
ans = (ans * tree[now][0].get(1, 0, (int)cway[now].size() - 1, 0, (int)cway[now].size() - 1)) % mod;
while(true){
int dist = getdist(x, now);
if(dist <= 40){
ans = (ans * megop[now][dist]) % mod;
}
if(now == top) break;
int up = cpr[now];
if(dist <= 40){
ans = (ans * tree[up][dist].get(1, 0, (int)cway[up].size() - 1, 0, ind[now] - 1)) % mod;
ans = (ans * tree[up][dist].get(1, 0, (int)cway[up].size() - 1, ind[now] + 1, (int)cway[up].size() - 1)) % mod;
}
now = up;
}
cout << ans << '\n';
}
}
return 0;
}
Compilation message
sprinkler.cpp: In member function 'void Seg::push(long long int, long long int, long long int, long long int, long long int)':
sprinkler.cpp:27:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int m = s + e >> 1;
| ~~^~~
sprinkler.cpp: In member function 'long long int Seg::get(long long int, long long int, long long int, long long int, long long int)':
sprinkler.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
285384 KB |
Output is correct |
| 2 |
Incorrect |
158 ms |
285248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
285196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
285196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
285340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
285296 KB |
Output is correct |
| 2 |
Execution timed out |
4116 ms |
756984 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
285384 KB |
Output is correct |
| 2 |
Incorrect |
158 ms |
285248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
