oj.uz

Submission #1090034

# Submission time Handle Problem Language Result Execution time Memory
1090034 2024-09-17T15:52:08 Z Neco_arc Sprinkler (JOI22_sprinkler) C++17
12 / 100
 603 ms 94904 KB 
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Sprinkler"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, q;
int par[maxn];
ll f[maxn][42], a[maxn];
vector<int> edges[maxn];

void pre_dfs(int u, int p) {
    for(int v : edges[u]) if(v != p) {
        par[v] = u;
        pre_dfs(v, u);
    }
}

void update(int x, int k, ll w) {
    int i;
    for(i = 0; i <= k && x != 0; ++i) {
        int remain = k - i;
        f[x][remain] = f[x][remain] * w % mod;
        if(remain - 1 >= 0) f[x][remain - 1] = f[x][remain - 1] * w % mod;
        x = par[x];
    }

    if(x == 0) {
        fi(t, 1, k - i) f[0][t] = f[0][t] * w % mod;
    }

}

ll get(int x) {
    ll ans = a[x], d = 0;
    fi(_, 0, 40) {
        ans = ans * f[x][d] ;
        x = par[x], ++d;
        if(x == 0) break;
    }
    if(x == 0) ans = ans * f[0][d] % mod;
    return ans;
}

void solve()
{
    cin >> n >> mod;
    fi(i, 1, n - 1) {
        int x, y; cin >> x >> y;
        edges[x].push_back(y), edges[y].push_back(x);
    }
    fi(i, 1, n) cin >> a[i];

    fi(i, 0, n) fi(j, 0, 41) f[i][j] = 1;
    pre_dfs(1, 0);

    cin >> q;
    fi(i, 1, q) {
        int type, x, k, w; cin >> type >> x;
        if(type == 1) cin >> k >> w, update(x, k, w);
        else cout << get(x) << '\n';
    }

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5032 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Incorrect 3 ms 5468 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 4956 KB Output is correct
2 Incorrect 414 ms 92016 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 4956 KB Output is correct
2 Incorrect 414 ms 92016 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 503 ms 92756 KB Output is correct
3 Correct 603 ms 92500 KB Output is correct
4 Correct 474 ms 92120 KB Output is correct
5 Correct 398 ms 88404 KB Output is correct
6 Correct 263 ms 88608 KB Output is correct
7 Correct 219 ms 88692 KB Output is correct
8 Correct 182 ms 89276 KB Output is correct
9 Correct 495 ms 91640 KB Output is correct
10 Correct 551 ms 93088 KB Output is correct
11 Correct 431 ms 88144 KB Output is correct
12 Correct 436 ms 89172 KB Output is correct
13 Correct 312 ms 89844 KB Output is correct
14 Correct 333 ms 90448 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 551 ms 94904 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 4956 KB Output is correct
2 Correct 2 ms 5032 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Incorrect 3 ms 5468 KB Output isn't correct
5 Halted 0 ms 0 KB -