Submission #590894

#	Time	Username	Problem	Language	Result	Execution time	Memory
590894		keta_tsimakuridze	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	713 ms	82832 KiB

sprinkler

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define endl "\n"
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, h[N], cn[N][42], p[N];
vector<int> V[N];
void dfs(int u, int P) {
    for(int i = 0; i < V[u].size(); i++) {
        if(V[u][i] != P) p[V[u][i]] = u, dfs(V[u][i], u);
    }
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, L;
    cin >> n >> L;
    for(int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
    }
    for(int i = n + 40; i > n; i--) {
        V[i].push_back(i - 1);
    }
    dfs(n + 40, 0);
    for(int i = 1; i <= n + 40; i++) {
        for(int d = 0; d <= 40; d++) cn[i][d] = 1;
    }
    for(int i = 1; i <= n; i++) cin >> h[i];
    int q;
    cin >> q;
    while(q--) {
        cin >> t;
        if(t == 1) {
            int x, d, w;
            cin >> x >> d >> w;
            // d1 + d2 = d,     d1 + (40 - d) + d2 = 40
            d = 40 - d;
            while(d <= 40) {
                cn[x][d] = (ll)cn[x][d] * w % L;
                ++d;
                x = p[x];
            }
            continue;
        }
        int x;
        cin >> x;
        int ans = h[x], d = 0;
        while(x && d <= 40){
            ans = (ll)ans * cn[x][40 - d] % L;
            if(d != 40) ans = (ll)ans * cn[x][39 - d] % L;
            ++d;
            x = p[x];
        }
        cout << ans << endl;
    }
}

Compilation message (stderr)

sprinkler.cpp: In function 'void dfs(int, int)':
sprinkler.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
sprinkler.cpp: At global scope:
sprinkler.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17