Submission #571685

#	Time	Username	Problem	Language	Result	Execution time	Memory
571685		maomao90	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1010 ms	73644 KiB

sprinkler

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 400005;
const int MAXD = 41;

int n, l;
vii adj[MAXN];
int h[MAXN];
int q;
int lz[MAXD][MAXN];

int p[MAXN];
void dfs(int u) {
    REP (i, 0, adj[u].size()) {
        if (adj[u][i].FI == p[u]) {
            swap(adj[u][i], adj[u][SZ(adj[u]) - 1]);
            break;
        }
    }
    for (auto &[v, id] : adj[u]) {
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
    }
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> l;
    REP (i, 1, n) {
        int a, b; cin >> a >> b;
        adj[a].pb({b, 0});
        adj[b].pb({a, 0});
    }
    dfs(1);
    REP (i, 1, n + 1) {
        cin >> h[i];
    }
    REP (i, 0, MAXD) {
        REP (j, 0, n + 1) {
            lz[i][j] = 1;
        }
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, d, w; cin >> x >> d >> w;
            int u = x;
            RREP (i, d, 0) {
                lz[i][u] = (ll) lz[i][u] * w % l;
                if (i) {
                    lz[i - 1][u] = (ll) lz[i - 1][u] * w % l;
                }
                if (p[u] == 0) {
                    RREP (j, i - 2, 0) {
                        lz[j][u] = (ll) lz[j][u] * w % l;
                    }
                    break;
                }
                u = p[u];
            }
        } else {
            int x; cin >> x;
            int ans = h[x];
            int u = x;
            REP (i, 0, MAXD) {
                ans = (ll) ans * lz[i][u] % l;
                if (p[u] == 0) {
                    break;
                }
                u = p[u];
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

/*
6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
2
1 4 1 9
2 1

4 7
1 2
2 3
3 4
1
1
1
1
2
1 1 0 2
2 1
*/

Compilation message (stderr)

sprinkler.cpp: In function 'void dfs(int)':
sprinkler.cpp:16:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   50 |     REP (i, 0, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
sprinkler.cpp:50:5: note: in expansion of macro 'REP'
   50 |     REP (i, 0, adj[u].size()) {
      |     ^~~

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