Submission #1208333

#TimeUsernameProblemLanguageResultExecution timeMemory
1208333salmonSprinkler (JOI22_sprinkler)C++20
100 / 100
2526 ms161760 KiB
#include <bits/stdc++.h> using namespace std; int N,Q; long long int mod; int st[200100][45 * 4]; vector<int> adjlst[200100]; int parent[200100]; int lst[200100]; int cont = 1; void build(int i, int s, int e, int it){ st[it][i] = 1; if(s != e){ int m = (s + e)/2; build(i * 2, s, m, it); build(i * 2 + 1, m + 1, e, it); } } void update(int i, int s, int e, int it, int S, int E, int k){ if(S <= s && e <= E){ st[it][i] = (long long int) st[it][i] * k % mod; return; } int m = (s + e)/2; if(S <= m){ update(i * 2, s, m, it, S , E, k); } if(m < E){ update(i * 2 + 1, m + 1, e, it, S, E, k); } } int query(int i, int s, int e, int it, int in){ if(s == e) return st[it][i]; int m = (s + e)/2; if(in <= m) return query(i * 2, s, m, it, in) * (long long int) st[it][i] % mod; else return query(i * 2 + 1, m + 1 , e, it , in) * (long long int) st[it][i] % mod; } void dfs(int i, int p){ parent[i] = p; for(int j : adjlst[i]){ if(j == p) continue; dfs(j,i); } } int main(){ scanf(" %d",&N); scanf(" %lld",&mod); for(int i = 0; i < N - 1; i++){ int u,v; scanf(" %d",&u); scanf(" %d",&v); adjlst[u].push_back(v); adjlst[v].push_back(u); } for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]); dfs(1,-1); for(int i = 1; i <= N; i++){ build(1,0,41,i); } scanf(" %d",&Q); for(int i = 0; i < Q; i++){ int h; scanf(" %d",&h); if(h == 1){ int X, D, W; scanf(" %d",&X); scanf(" %d",&D); scanf(" %d",&W); while(X != 1 && D >= 0){ update(1,0,41,X,D - 1, D, W); X = parent[X]; D -= 1; } if(X == 1 && D >= 0){ update(1,0,41,X,0,D,W); } } else{ int X; scanf(" %d",&X); int num = lst[X]; int D = 0; for(int i = 0; i < 41; i++){ num = query(1,0,41,X,D) * (long long int) num % mod; if(X == 1) break; D++; X = parent[X]; } printf("%d\n",num ); } } }

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
sprinkler.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf(" %lld",&mod);
      |         ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
sprinkler.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~
sprinkler.cpp:74:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]);
      |                                     ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
sprinkler.cpp:87:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~
sprinkler.cpp:92:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |                         scanf(" %d",&X);
      |                         ~~~~~^~~~~~~~~~
sprinkler.cpp:93:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |                         scanf(" %d",&D);
      |                         ~~~~~^~~~~~~~~~
sprinkler.cpp:94:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                         scanf(" %d",&W);
      |                         ~~~~~^~~~~~~~~~
sprinkler.cpp:109:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |                         scanf(" %d",&X);
      |                         ~~~~~^~~~~~~~~~
#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...