Submission #617436

#TimeUsernameProblemLanguageResultExecution timeMemory
617436patrikpavic2Sprinkler (JOI22_sprinkler)C++17
41 / 100
4113 ms686264 KiB
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define X first #define Y second #define PB push_back using namespace std; typedef vector < int > vi; typedef long long ll; const int N = 2e5 + 500; const int LOG = 20; const int INF = 0x3f3f3f3f; int MOD; inline int mul(int A, int B){ return (ll)A * B % MOD; } struct tournament{ int siz, off; vi T; void init(int _siz){ siz = _siz; off = 1; while(off < siz) off <<= 1; T.resize(2 * off); for(int &x : T) x = 1; } int get(int x){ int ret = 1; for(x = (x + off); x ; x /= 2) ret = mul(ret, T[x]); return ret; } void Tmultiply(int i, int a, int b, int lo, int hi, int x){ if(lo <= a && b <= hi) { T[i] = mul(T[i], x); return; } if(a > hi || b < lo) return; Tmultiply(2 * i, a, (a + b) / 2, lo, hi, x); Tmultiply(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x); } inline void multiply(int l, int r, int x){ if(r < l ) return; Tmultiply(1, 0, off - 1, l, r, x); } }; tournament T[N][41]; int cen[N], siz[N], par[N], dep[N][LOG], gore[N], tko[N][41]; vector < int > pos; int L[N][41], R[N][41], gdje[N][LOG], osb[N], gdje2[N][LOG]; int n, q; vector < int > v[N]; void dfs(int x, int lst){ siz[x] = 1; pos.PB(x); for(int y : v[x]){ if(cen[y] != INF || y == lst) continue; dfs(y, x); siz[x] += siz[y]; } } int TATA, RAZ; void dfs2(int x, int lst, int dis){ gdje2[x][RAZ] = dis; if(dis <= 40) { gdje[x][RAZ] = tko[TATA][dis]; tko[TATA][dis]++; } for(int y : v[x]){ if(y == lst || cen[y] <= RAZ) continue; dfs2(y, x, dis + 1); } } int nadi_centroid(int x){ pos.clear(); dfs(x, x); int bst = x; for(int y : pos) if(2 * siz[y] >= (int)pos.size() && siz[y] < siz[bst]) bst = y; return bst; } int centroidna(int x, int dub){ x = nadi_centroid(x); cen[x] = dub; for(int y : v[x]){ if(cen[y] != INF) continue; int nov = centroidna(y, dub + 1); for(int i = 1;i <= 40;i++) L[nov][i] = tko[x][i]; TATA = x; RAZ = dub; dfs2(y, x, 1); for(int i = 1;i <= 40;i++) R[nov][i] = tko[x][i] - 1; par[nov] = x; } return x; } void obradi(int x, int d, int k){ osb[x] = mul(osb[x], k); for(int i = 1;i <= d;i++) T[x][i].multiply(0, T[x][i].siz - 1, k); int lst = x, poc = x; x = par[x]; while(x){ if(gdje2[poc][cen[x]] <= d) osb[x] = mul(osb[x], k); for(int i = 1;i <= d - gdje2[poc][cen[x]];i++){ T[x][i].multiply(0, L[lst][i] - 1, k); T[x][i].multiply(R[lst][i] + 1, T[x][i].siz - 1, k); } lst = x; x = par[x]; } } int get(int x){ int ret = osb[x]; int cur = x; while(cur){ if(gdje[x][cen[cur]] != -1){ ret = mul(ret, T[cur][gdje2[x][cen[cur]]].get(gdje[x][cen[cur]])); } cur = par[cur]; } return ret; } int main(){ memset(cen, INF, sizeof(cen)); memset(gdje, -1, sizeof(gdje)); scanf("%d%d", &n, &MOD); for(int i = 1;i < n;i++){ int x, y; scanf("%d%d", &x, &y); v[x].PB(y), v[y].PB(x); } for(int i = 1;i <= n;i++) scanf("%d", osb + i); centroidna(1, 1); for(int i = 1;i <= n;i++) for(int j = 0;j <= 40;j++) T[i][j].init(tko[i][j]); scanf("%d", &q); for(;q--;){ int ty; scanf("%d", &ty); if(ty == 2){ int x; scanf("%d", &x); printf("%d\n", get(x)); } else{ int x, d, k; scanf("%d%d%d", &x, &d, &k); obradi(x, d, k); } } return 0; }

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d%d", &n, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:143:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%d", osb + i);
      |   ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
sprinkler.cpp:154:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
sprinkler.cpp:156:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
sprinkler.cpp:160:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |    int x, d, k; scanf("%d%d%d", &x, &d, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...