oj.uz

Submission #736107

# Submission time Handle Problem Language Result Execution time Memory
736107 2023-05-05T08:32:09 Z Sam_a17 Sprinkler (JOI22_sprinkler) C++17
50 / 100
 467 ms 31052 KB 
#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;
  }

  d1[0] = d2[0] = 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;
          h[u] *= w;
          h[u] %= l;
        // }

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

        d2[x] *= w;
        d2[x] %= l;

        d1[x] *= w;
        d1[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;
        // }

        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 428 ms 21964 KB Output is correct
3 Correct 331 ms 18788 KB Output is correct
4 Correct 413 ms 23492 KB Output is correct
5 Correct 395 ms 20396 KB Output is correct
6 Correct 314 ms 20300 KB Output is correct
7 Correct 279 ms 20608 KB Output is correct
8 Correct 215 ms 20984 KB Output is correct
9 Correct 461 ms 26428 KB Output is correct
10 Correct 329 ms 23020 KB Output is correct
11 Correct 432 ms 21992 KB Output is correct
12 Correct 278 ms 18684 KB Output is correct
13 Correct 198 ms 19292 KB Output is correct
14 Correct 216 ms 19392 KB Output is correct
15 Correct 208 ms 19288 KB Output is correct
16 Correct 214 ms 19372 KB Output is correct
17 Correct 236 ms 19852 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 4 ms 5032 KB Output is correct
21 Correct 4 ms 5040 KB Output is correct
22 Correct 3 ms 5040 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 428 ms 21964 KB Output is correct
3 Correct 331 ms 18788 KB Output is correct
4 Correct 413 ms 23492 KB Output is correct
5 Correct 395 ms 20396 KB Output is correct
6 Correct 314 ms 20300 KB Output is correct
7 Correct 279 ms 20608 KB Output is correct
8 Correct 215 ms 20984 KB Output is correct
9 Correct 461 ms 26428 KB Output is correct
10 Correct 329 ms 23020 KB Output is correct
11 Correct 432 ms 21992 KB Output is correct
12 Correct 278 ms 18684 KB Output is correct
13 Correct 198 ms 19292 KB Output is correct
14 Correct 216 ms 19392 KB Output is correct
15 Correct 208 ms 19288 KB Output is correct
16 Correct 214 ms 19372 KB Output is correct
17 Correct 236 ms 19852 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 4 ms 5032 KB Output is correct
21 Correct 4 ms 5040 KB Output is correct
22 Correct 3 ms 5040 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 431 ms 22004 KB Output is correct
25 Correct 339 ms 19848 KB Output is correct
26 Correct 407 ms 25804 KB Output is correct
27 Correct 375 ms 21320 KB Output is correct
28 Correct 303 ms 21460 KB Output is correct
29 Correct 279 ms 21416 KB Output is correct
30 Correct 212 ms 22008 KB Output is correct
31 Correct 442 ms 26072 KB Output is correct
32 Correct 362 ms 24040 KB Output is correct
33 Correct 447 ms 22868 KB Output is correct
34 Correct 324 ms 19696 KB Output is correct
35 Correct 3 ms 5076 KB Output is correct
36 Correct 4 ms 5028 KB Output is correct
37 Correct 3 ms 4948 KB Output is correct
38 Correct 3 ms 5076 KB Output is correct
39 Correct 3 ms 4948 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 4 ms 5040 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 4 ms 4948 KB Output is correct
45 Correct 4 ms 5028 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 5076 KB Output is correct
48 Correct 3 ms 4948 KB Output is correct
49 Correct 3 ms 5076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 289 ms 23936 KB Output is correct
3 Correct 467 ms 22028 KB Output is correct
4 Correct 326 ms 22640 KB Output is correct
5 Correct 300 ms 26628 KB Output is correct
6 Correct 272 ms 26716 KB Output is correct
7 Correct 320 ms 26904 KB Output is correct
8 Correct 194 ms 27536 KB Output is correct
9 Correct 293 ms 29584 KB Output is correct
10 Correct 461 ms 31052 KB Output is correct
11 Correct 281 ms 26232 KB Output is correct
12 Correct 433 ms 27180 KB Output is correct
13 Correct 310 ms 28036 KB Output is correct
14 Correct 303 ms 28572 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5032 KB Output is correct
17 Correct 3 ms 5028 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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