Submission #590737

#	Time	Username	Problem	Language	Result	Execution time	Memory
590737		Ronin13	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1049 ms	98552 KiB

sprinkler

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define epb emplace_back
using namespace std;


ll mod;
const int NMAX = 2e5 + 1;
vector <vector <int> > g(NMAX);
vector <int >p(NMAX);
const int KMAX = 41;
ll d[NMAX][KMAX];

void dfs(int v, int e = -1){
    p[v] = e;
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    cin >> mod;
    ll h[n + 1];
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0 ; j < KMAX; j++) d[i][j] = 1;
    }
    for(int i= 1; i <= n; i++){
        cin >> h[i];
    }
    dfs(1);
    int q; cin >> q;
    while(q--){
        int type; cin >> type;
        if(type == 1){
            int v;
            cin >> v;
            int dd; cin >> dd;
            ll w; cin >> w;
            vector <pii> vec;
            int cur = v;
            int cur1 = dd;
            while(vec.size() <= dd){
                vec.pb({cur, cur1});
                cur = p[cur];
                if(cur == -1) break;
                cur1--;
            }
            reverse(vec.begin(), vec.end());
            for(int i = 0; i <= vec[0].s; i++){
                int x = vec[0].f;
                d[x][i] *= w;
                d[x][i] %= mod;
            }
            for(int i = 1; i < vec.size(); i++){
                int x = vec[i].f;
                int y = vec[i].s;
                d[x][y - 1] *= w;
                d[x][y - 1] %= mod;
                d[x][y] *= w;
                d[x][y] %= mod;
            }
            /*for(int i = 1; i <= n; i++){
                for(int j = 0; j <= 40; j++){
                    cout << d[i][j] << ' ';
                }
                cout << "\n";
            }*/
        }
        if(type == 2){
            int v; cin >> v;
            vector <int> vec;
            int cur = v;
            while(cur != -1 && vec.size() <= 40){
                vec.pb(cur);
                cur = p[cur];
            }
            ll ans = 1;
            for(int i = 0; i < vec.size(); i++){
                int x = vec[i];
                ans *= d[x][i];
                ans %= mod;
            }
            ans *= h[v];
            ans %= mod;
            cout << ans << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:56:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |             while(vec.size() <= dd){
      |                   ~~~~~~~~~~~^~~~~
sprinkler.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i = 1; i < vec.size(); i++){
      |                            ~~^~~~~~~~~~~~
sprinkler.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for(int i = 0; i < vec.size(); i++){
      |                            ~~^~~~~~~~~~~~

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