Submission #736085

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736085	2023-05-05T08:06:52 Z	Sam_a17	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	291 ms	25924 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	2 ms	4980 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	280 ms	21192 KB	Output is correct
3	Correct	264 ms	17984 KB	Output is correct
4	Correct	261 ms	22532 KB	Output is correct
5	Correct	250 ms	19532 KB	Output is correct
6	Correct	249 ms	19484 KB	Output is correct
7	Correct	270 ms	19860 KB	Output is correct
8	Correct	187 ms	20200 KB	Output is correct
9	Correct	260 ms	25924 KB	Output is correct
10	Correct	291 ms	22132 KB	Output is correct
11	Correct	251 ms	21056 KB	Output is correct
12	Correct	284 ms	17956 KB	Output is correct
13	Correct	191 ms	18560 KB	Output is correct
14	Correct	210 ms	18652 KB	Output is correct
15	Correct	204 ms	18548 KB	Output is correct
16	Correct	198 ms	18468 KB	Output is correct
17	Correct	221 ms	19148 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	280 ms	21192 KB	Output is correct
3	Correct	264 ms	17984 KB	Output is correct
4	Correct	261 ms	22532 KB	Output is correct
5	Correct	250 ms	19532 KB	Output is correct
6	Correct	249 ms	19484 KB	Output is correct
7	Correct	270 ms	19860 KB	Output is correct
8	Correct	187 ms	20200 KB	Output is correct
9	Correct	260 ms	25924 KB	Output is correct
10	Correct	291 ms	22132 KB	Output is correct
11	Correct	251 ms	21056 KB	Output is correct
12	Correct	284 ms	17956 KB	Output is correct
13	Correct	191 ms	18560 KB	Output is correct
14	Correct	210 ms	18652 KB	Output is correct
15	Correct	204 ms	18548 KB	Output is correct
16	Correct	198 ms	18468 KB	Output is correct
17	Correct	221 ms	19148 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	-