oj.uz

Submission #735841

# Submission time Handle Problem Language Result Execution time Memory
735841 2023-05-04T19:20:57 Z Sam_a17 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 25288 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;

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 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];
  }

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

    if(type == 1) {
      long long x, d, w;
      cin >> x >> d >> w;
      bfs(x, d, w);
    } else {
      long long x; cin >> x;
      cout << h[x] << '\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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 4 ms 5020 KB Output is correct
4 Correct 5 ms 5088 KB Output is correct
5 Correct 7 ms 5076 KB Output is correct
6 Correct 15 ms 5100 KB Output is correct
7 Correct 16 ms 5040 KB Output is correct
8 Correct 14 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5028 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 4996 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5028 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 3 ms 5024 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 4 ms 4948 KB Output is correct
24 Correct 4 ms 5028 KB Output is correct
25 Correct 4 ms 5024 KB Output is correct
26 Correct 3 ms 5028 KB Output is correct
27 Correct 4 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 278 ms 24720 KB Output is correct
3 Correct 672 ms 25212 KB Output is correct
4 Correct 504 ms 24876 KB Output is correct
5 Correct 508 ms 25008 KB Output is correct
6 Correct 440 ms 24496 KB Output is correct
7 Correct 415 ms 25288 KB Output is correct
8 Execution timed out 4048 ms 18876 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 278 ms 24720 KB Output is correct
3 Correct 672 ms 25212 KB Output is correct
4 Correct 504 ms 24876 KB Output is correct
5 Correct 508 ms 25008 KB Output is correct
6 Correct 440 ms 24496 KB Output is correct
7 Correct 415 ms 25288 KB Output is correct
8 Execution timed out 4048 ms 18876 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 800 ms 21632 KB Output is correct
3 Execution timed out 4032 ms 21432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 852 ms 24380 KB Output is correct
3 Execution timed out 4032 ms 21692 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 4 ms 5020 KB Output is correct
4 Correct 5 ms 5088 KB Output is correct
5 Correct 7 ms 5076 KB Output is correct
6 Correct 15 ms 5100 KB Output is correct
7 Correct 16 ms 5040 KB Output is correct
8 Correct 14 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5028 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 4996 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5028 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 3 ms 5024 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 4 ms 4948 KB Output is correct
24 Correct 4 ms 5028 KB Output is correct
25 Correct 4 ms 5024 KB Output is correct
26 Correct 3 ms 5028 KB Output is correct
27 Correct 4 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 4 ms 4948 KB Output is correct
30 Correct 278 ms 24720 KB Output is correct
31 Correct 672 ms 25212 KB Output is correct
32 Correct 504 ms 24876 KB Output is correct
33 Correct 508 ms 25008 KB Output is correct
34 Correct 440 ms 24496 KB Output is correct
35 Correct 415 ms 25288 KB Output is correct
36 Execution timed out 4048 ms 18876 KB Time limit exceeded
37 Halted 0 ms 0 KB -