oj.uz

Submission #1090033

# Submission time Handle Problem Language Result Execution time Memory
1090033 2024-09-17T15:48:11 Z Neco_arc Sprinkler (JOI22_sprinkler) C++17
12 / 100
 587 ms 93320 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][41], 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, 40) 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 4952 KB Output is correct
2 Correct 3 ms 4964 KB Output is correct
3 Correct 3 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 90476 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 90476 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 3 ms 4952 KB Output is correct
2 Correct 527 ms 91236 KB Output is correct
3 Correct 587 ms 90960 KB Output is correct
4 Correct 462 ms 90704 KB Output is correct
5 Correct 385 ms 87112 KB Output is correct
6 Correct 237 ms 87124 KB Output is correct
7 Correct 226 ms 87120 KB Output is correct
8 Correct 178 ms 87748 KB Output is correct
9 Correct 496 ms 89948 KB Output is correct
10 Correct 538 ms 91472 KB Output is correct
11 Correct 446 ms 86660 KB Output is correct
12 Correct 482 ms 87380 KB Output is correct
13 Correct 318 ms 88400 KB Output is correct
14 Correct 336 ms 88916 KB Output is correct
15 Correct 2 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 4956 KB Output is correct
2 Incorrect 536 ms 93320 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 4952 KB Output is correct
2 Correct 3 ms 4964 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Incorrect 3 ms 5468 KB Output isn't correct
5 Halted 0 ms 0 KB -