# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
555883 | 600Mihnea | Sprinkler (JOI22_sprinkler) | C++17 | 4083 ms | 90888 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
bool home = 1;
using namespace std;
typedef long long ll;
const int N=200000+7;
const int K=20;
int n;
int q;
int mod;
int h[N];
vector<int> g[N];
pair<int, int> rmq[K][2*N];
int lg[2*N];
int dep[N];
int first[N];
int last[N];
int top;
void build(int a,int p=-1){
rmq[0][++top]={dep[a], a};
first[a]=last[a]=top;
for(auto&b:g[a]){
if(b==p) continue;
dep[b]=1+dep[a];
build(b,a);
rmq[0][++top]={dep[a], a};
last[a]=top;
}
}
int get_lca(int a,int b){
if(first[a]>last[b]) swap(a,b);
a=first[a];
b=last[b];
assert(a<=b);
int k=lg[b-a+1];
return min(rmq[k][a],rmq[k][b-(1<<k)+1]).second;
}
int get_dist(int a,int b){
int c=get_lca(a,b);
return dep[a]+dep[b]-2*dep[c];
}
signed main() {
#ifdef ONLINE_JUDGE
home = 0;
#endif
home=0;
if (home) {
freopen("I_am_iron_man", "r", stdin);
}
else {
ios::sync_with_stdio(0); cin.tie(0);
}
cin>>n>>mod;
for (int i=1;i<n;i++) {
int a, b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
build(1);
for(int i=2;i<=top;i++) lg[i]=1+lg[i/2];
for (int k=1;(1<<k)<=top;k++) {
for(int i=1;i+(1<<k)-1<=top;i++){
rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<<(k-1))]);
}
}
for (int i=1;i<=n;i++) {
cin>>h[i];
}
cin>>q;
while(q--){
int type;
cin>>type;
assert(type==1||type==2);
if(type==1){
int x,d,w;
cin>>x>>d>>w;
for (int i=1;i<=n;i++){
if(get_dist(x,i)<=d){
h[i]=h[i]*(ll)w%mod;
}
}
}else{
int x;
cin>>x;
cout<<h[x]<<"\n";
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |