oj.uz

Submission #1025242

# Submission time Handle Problem Language Result Execution time Memory
1025242 2024-07-16T18:14:29 Z underwaterkillerwhale Sprinkler (JOI22_sprinkler) C++17
42 / 100
 694 ms 61148 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
int Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 137;

int n, Q;
int a[N];
int val[N][42], par[N];
vector<int> ke[N];

void dfs (int u, int p){
    par[u] = p;
    iter (&v, ke[u]) {
        if (v != p) dfs (v, u);
    }
}
void update (int u, int d, ll w, int h = 0) {
    if (h > d) return;
    (val[u][d - h] *= w) %= Mod;
    update (par[u], d, w, h + 1);
}

int get (int x, int de) {
    if (de == 41) return 1;
    if (x == 1) {
        return val[1][de];
    }
    return 1LL * val[x][de] * val[x][de + 1] % Mod * get (par[x], de + 1) % Mod;
}

void solution () {
    cin >> n >> Mod;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    rep (i, 1, n) rep (j, 1, 41) val[i][j] = 1;
    rep (i, 1, n) cin >> a[i], val[i][0] = a[i];
    dfs (1, 0);
    par[1] = 1;
    cin >> Q;
    rep (i, 1, Q) {
        int typ; cin >> typ;
        if (typ == 1) {
            ll x, d, w;
            cin >>x >> d >> w;
            update (x, d, w);
        }
        else {
            ll x;
            cin >> x;
            cout << get (x, 0) <<"\n";
        }
    }
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*

*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Incorrect 2 ms 5208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 611 ms 49440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 611 ms 49440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 694 ms 51024 KB Output is correct
3 Correct 569 ms 58448 KB Output is correct
4 Correct 565 ms 58128 KB Output is correct
5 Correct 445 ms 54868 KB Output is correct
6 Correct 265 ms 55012 KB Output is correct
7 Correct 291 ms 55120 KB Output is correct
8 Correct 273 ms 55608 KB Output is correct
9 Correct 692 ms 57624 KB Output is correct
10 Correct 481 ms 58960 KB Output is correct
11 Correct 453 ms 54620 KB Output is correct
12 Correct 418 ms 55368 KB Output is correct
13 Correct 229 ms 56404 KB Output is correct
14 Correct 243 ms 56668 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 6560 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 568 ms 52124 KB Output is correct
3 Correct 461 ms 55464 KB Output is correct
4 Correct 453 ms 58952 KB Output is correct
5 Correct 403 ms 56456 KB Output is correct
6 Correct 251 ms 56500 KB Output is correct
7 Correct 240 ms 56332 KB Output is correct
8 Correct 175 ms 56652 KB Output is correct
9 Correct 566 ms 61148 KB Output is correct
10 Correct 460 ms 59792 KB Output is correct
11 Correct 474 ms 57216 KB Output is correct
12 Correct 451 ms 55788 KB Output is correct
13 Correct 284 ms 56408 KB Output is correct
14 Correct 293 ms 57148 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 1 ms 6744 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4996 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Incorrect 2 ms 5208 KB Output isn't correct
5 Halted 0 ms 0 KB -