oj.uz

Submission #792085

# Submission time Handle Problem Language Result Execution time Memory
792085 2023-07-24T14:56:56 Z quanlt206 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 690 ms 186348 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define MASK(x) (1LL << (x))
#define all(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 2e5 + 7;

int n, L, P[N];

ll res[N][50], h[N], res2[N][50];

vector<int> v[N];

void dfs(int x, int par) {
    P[x] = par;
    for (auto y : v[x])
        if (y != par) dfs(y, x);
}

void firstQuery() {
    int x, d, w;
    cin>>x>>d>>w;
    FOR(j, 0, d) res2[x][j] = res2[x][j] * w % L;
    int tmp = 1;
    x = P[x];
    while (x != -1 && tmp <= d) {
        res[x][d - tmp] = res[x][d - tmp] * w % L;
        tmp++;
        x = P[x];
    }
}

void secondQuery() {
    int x;
    cin>>x;
    ll ans = h[x];
    int tmp = 1;
    int last_x = x;
    ans = ans * res2[x][0] % L;
    FOR(i, 0, 40) ans = ans * res[x][i] % L;
    x = P[x];
//    cout<<x<<" "<<ans<<"\n";
    while (x != -1 && tmp <= 40) {
        ans = ans * res2[x][tmp] % L;
//        cout<<x<<" "<<ans<<"\n";
//        ans = ans * res[x][0] % L;
        if (tmp < 40) {
            for (auto y : v[x])
                if (y != last_x && y != P[x]) {
                    FOR(j, 0, 40)
                        if (j >= tmp + 1) {
                            ans = ans * res[y][j] % L;
                            cout<<y<<" "<<j<<" "<<res[y][j]<<"\n";
                        }
                        else break;
                }
        }
//        cout<<x<<" "<<ans<<"\n";
//        break;
        last_x = x;
        x = P[x];
        tmp++;
    }
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>L;
//    L = 1000;
    REP(i, 1, n) {
        int x, y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    FOR(i, 1, n)
        FOR(j, 0, 40) res[i][j] = res2[i][j] = 1;
    FOR(i, 1, n) cin>>h[i];
    dfs(1, -1);
    int Q;
    cin>>Q;
    while (Q--) {
        int type;
        cin>>type;
        if (type == 1) firstQuery(); else secondQuery();
    }
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5020 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 4 ms 5844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 641 ms 182020 KB Output is correct
3 Correct 346 ms 182612 KB Output is correct
4 Correct 509 ms 185064 KB Output is correct
5 Correct 462 ms 182244 KB Output is correct
6 Correct 359 ms 181768 KB Output is correct
7 Correct 364 ms 182520 KB Output is correct
8 Correct 319 ms 183020 KB Output is correct
9 Correct 684 ms 186220 KB Output is correct
10 Correct 353 ms 186348 KB Output is correct
11 Correct 588 ms 181916 KB Output is correct
12 Correct 346 ms 182500 KB Output is correct
13 Correct 228 ms 182824 KB Output is correct
14 Correct 230 ms 183224 KB Output is correct
15 Correct 226 ms 182668 KB Output is correct
16 Correct 235 ms 183188 KB Output is correct
17 Correct 252 ms 183720 KB Output is correct
18 Correct 2 ms 5076 KB Output is correct
19 Correct 3 ms 5040 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 4960 KB Output is correct
22 Correct 2 ms 5076 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 641 ms 182020 KB Output is correct
3 Correct 346 ms 182612 KB Output is correct
4 Correct 509 ms 185064 KB Output is correct
5 Correct 462 ms 182244 KB Output is correct
6 Correct 359 ms 181768 KB Output is correct
7 Correct 364 ms 182520 KB Output is correct
8 Correct 319 ms 183020 KB Output is correct
9 Correct 684 ms 186220 KB Output is correct
10 Correct 353 ms 186348 KB Output is correct
11 Correct 588 ms 181916 KB Output is correct
12 Correct 346 ms 182500 KB Output is correct
13 Correct 228 ms 182824 KB Output is correct
14 Correct 230 ms 183224 KB Output is correct
15 Correct 226 ms 182668 KB Output is correct
16 Correct 235 ms 183188 KB Output is correct
17 Correct 252 ms 183720 KB Output is correct
18 Correct 2 ms 5076 KB Output is correct
19 Correct 3 ms 5040 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 3 ms 4960 KB Output is correct
22 Correct 2 ms 5076 KB Output is correct
23 Correct 2 ms 5028 KB Output is correct
24 Incorrect 581 ms 182036 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5020 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 4 ms 5844 KB Output isn't correct
5 Halted 0 ms 0 KB -