Submission #555883

#TimeUsernameProblemLanguageResultExecution timeMemory
555883600MihneaSprinkler (JOI22_sprinkler)C++17
3 / 100
4083 ms90888 KiB
#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)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...