Submission #736082

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736082	2023-05-05T08:01:44 Z	Sam_a17	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	483 ms	25720 KB

sprinkler

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
vector<int> adj[N];
long long n, l, h[N], q;
long long d1[N], d2[N];
int dd[N];
int p[N];

void bfs(int node, int dist, long long m) {
  queue<pair<int, int>> q;
  q.push({node, 0});
  vector<bool> used(n + 1);
  used[node] = true;
  q.push({node, 0});
  h[node] = (h[node] * m) % l;

  while (!q.empty()) {
    auto u = q.front();
    q.pop();

    for(auto i: adj[u.first]) {
      if(used[i]) continue;
      used[i] = true;
      if(u.second + 1 <= dist) {
        h[i] = (h[i] * m) % l;
        q.push({i, u.second + 1});
      }
    }
  }
}

void dfs(int node, int parent) {
  p[node] = parent;
  for(auto i: adj[node]) {
    if(i == parent) continue;
    dfs(i, node);
  }
}

void solve_() {
  cin >> n >> l;

  for(int i = 1; i <= n - 1; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  for(int i = 1; i <= n; i++) {
    cin >> h[i], dd[i] = -1;
    d1[i] = d2[i] = 1;
  }

  dfs(1, 0);

  cin >> q;
  while(q--) {
    int type; cin >> type;

    if(type == 1) {
      long long x, d, w;
      cin >> x >> d >> w;

      if(d == 0) {
        h[x] *= w;
        h[x] %= l;
      }
      else if(d == 1) {
        h[x] *= w;
        h[x] %= l;

        if(p[x]) {
          h[p[x]] *= w;
          h[p[x]] %= l;
        }

        d1[x] *= w;
        d1[x] %= l;
      } else if(d == 2) {
        int u = p[x], uu = p[p[x]];

        if(u) {
          d1[u] *= w;
          d1[u] %= l;
        }

        if(uu) {
          h[uu] *= w;
          h[uu] %= l;
        }

        d2[x] *= w;
        d2[x] %= l;
      } else {
        int cnt = d;
        while(x != 0 && cnt >= 0) {
          dd[x] = max(dd[x], cnt);
          cnt--, x = p[x];
        }
      }
    } else {
      long long x; cin >> x;
      long long cur = x;

      int cnt = 0, ok = 0;
      while(x != 0 && cnt < 41) {
        if(dd[x] != -1 && dd[x] >= cnt) {
          ok = 1;
          break;
        }
        x = p[x];
        cnt++;
      }

      if(ok) {
        cout << 0 << '\n';
      } else {
        long long ans = h[cur];

        int u = p[cur], uu = p[p[cur]];
        if(u) {
          ans *= d1[u];
          ans %= l;

          ans *= d2[u];
          ans %= l;
        }

        if(uu) {
          ans *= d2[uu];
          ans %= l;
        }
        cout << ans << '\n';
      }
    }
  }

}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

sprinkler.cpp: In function 'void setIO(std::string)':
sprinkler.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	4948 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	413 ms	21096 KB	Output is correct
3	Correct	311 ms	17964 KB	Output is correct
4	Correct	385 ms	22596 KB	Output is correct
5	Correct	358 ms	19560 KB	Output is correct
6	Correct	272 ms	19432 KB	Output is correct
7	Correct	295 ms	19792 KB	Output is correct
8	Correct	186 ms	20216 KB	Output is correct
9	Correct	483 ms	25720 KB	Output is correct
10	Correct	285 ms	22248 KB	Output is correct
11	Correct	410 ms	21220 KB	Output is correct
12	Correct	271 ms	17996 KB	Output is correct
13	Correct	204 ms	18520 KB	Output is correct
14	Correct	213 ms	18648 KB	Output is correct
15	Correct	201 ms	18552 KB	Output is correct
16	Correct	216 ms	18540 KB	Output is correct
17	Correct	224 ms	19152 KB	Output is correct
18	Correct	3 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	413 ms	21096 KB	Output is correct
3	Correct	311 ms	17964 KB	Output is correct
4	Correct	385 ms	22596 KB	Output is correct
5	Correct	358 ms	19560 KB	Output is correct
6	Correct	272 ms	19432 KB	Output is correct
7	Correct	295 ms	19792 KB	Output is correct
8	Correct	186 ms	20216 KB	Output is correct
9	Correct	483 ms	25720 KB	Output is correct
10	Correct	285 ms	22248 KB	Output is correct
11	Correct	410 ms	21220 KB	Output is correct
12	Correct	271 ms	17996 KB	Output is correct
13	Correct	204 ms	18520 KB	Output is correct
14	Correct	213 ms	18648 KB	Output is correct
15	Correct	201 ms	18552 KB	Output is correct
16	Correct	216 ms	18540 KB	Output is correct
17	Correct	224 ms	19152 KB	Output is correct
18	Correct	3 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct
23	Incorrect	3 ms	4948 KB	Output isn't correct
24	Halted	0 ms	0 KB	-