답안 #736079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736079	2023-05-05T07:59:51 Z	Sam_a17	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	432 ms	25620 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;
        }

        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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	4948 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	397 ms	21188 KB	Output is correct
3	Correct	251 ms	17884 KB	Output is correct
4	Correct	356 ms	22672 KB	Output is correct
5	Correct	342 ms	19516 KB	Output is correct
6	Correct	274 ms	19616 KB	Output is correct
7	Correct	283 ms	19756 KB	Output is correct
8	Correct	184 ms	20304 KB	Output is correct
9	Correct	432 ms	25620 KB	Output is correct
10	Correct	316 ms	22136 KB	Output is correct
11	Correct	405 ms	21060 KB	Output is correct
12	Correct	299 ms	18252 KB	Output is correct
13	Correct	212 ms	18624 KB	Output is correct
14	Correct	205 ms	18576 KB	Output is correct
15	Correct	192 ms	18640 KB	Output is correct
16	Correct	208 ms	18636 KB	Output is correct
17	Correct	215 ms	19240 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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	397 ms	21188 KB	Output is correct
3	Correct	251 ms	17884 KB	Output is correct
4	Correct	356 ms	22672 KB	Output is correct
5	Correct	342 ms	19516 KB	Output is correct
6	Correct	274 ms	19616 KB	Output is correct
7	Correct	283 ms	19756 KB	Output is correct
8	Correct	184 ms	20304 KB	Output is correct
9	Correct	432 ms	25620 KB	Output is correct
10	Correct	316 ms	22136 KB	Output is correct
11	Correct	405 ms	21060 KB	Output is correct
12	Correct	299 ms	18252 KB	Output is correct
13	Correct	212 ms	18624 KB	Output is correct
14	Correct	205 ms	18576 KB	Output is correct
15	Correct	192 ms	18640 KB	Output is correct
16	Correct	208 ms	18636 KB	Output is correct
17	Correct	215 ms	19240 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	-