oj.uz

Submission #568227

# Submission time Handle Problem Language Result Execution time Memory
568227 2022-05-25T02:00:45 Z maomao90 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 156628 KB 
// 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;

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 = 200005;
const int MAXD = 41;

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

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

void fwincre(int i, int x, int *fw) {
    for (; i <= MAXD; i += i & -i) fw[i] = (ll) fw[i] * x % l;
}
int fwqry(int i, int *fw) {
    int res = 1;
    for (; i > 0; i -= i & -i) res = (ll) res * fw[i] % l;
    return res;
}

int st[MAXN * 4][MAXD + 1];
void incre(int p, int l, int x) {
    int u = p + m;
    while (u) {
        fwincre(l, x, st[u]);
        u >>= 1;
    }
}
int qry(int s, int e, int l) {
    int a = s + m, b = e + m;
    int res = 1;
    while (a < b) {
        if (a & 1) {
            res = (ll) res * fwqry(l, st[a]) % ::l;
            a++;
        }
        if (b & 1) {
            b--;
            res = (ll) res * fwqry(l, st[b]) % ::l;
        }
        a >>= 1; b >>= 1;
    }
    return res;
}

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});
    }
    int on = n;
    REP (i, 2, n + 1) {
        if (adj[i].size() == 1) {
            adj[i].pb({++on, 0});
            adj[on].pb({i, 0});
        }
    }
    dfs(1);
    m = 1;
    while (m < ptr) {
        m <<= 1;
    }
    REP (i, 0, MAXN * 4) {
        REP (j, 0, MAXD + 1) {
            st[i][j] = 1;
        }
    }
    REP (i, 1, n + 1) {
        cin >> h[i];
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, d, w; cin >> x >> d >> w;
            int u = x;
            REP (i, MAXD - d + 1, MAXD + 1) {
                if (p[u].FI == 0) break;
                int id = p[u].SE;
                u = p[u].FI;
                cerr << "+ " << id << ' ' << i << ' ' << w << '\n';
                incre(id, i, w);
            }
            u = x;
            REP (i, MAXD - d, MAXD + 1) {
                if (adj[u][0].FI == p[u].FI) break;
                int id = adj[u][0].SE;
                u = adj[u][0].FI;
                cerr << "+ " << id << ' ' << i << ' ' << w << '\n';
                incre(id, i, w);
            }
        } else {
            int x; cin >> x;
            ll ans = h[x];
            ans = ans * qry(pre[x], pst[x], MAXD) % l;
            int u = x;
            RREP (i, MAXD - 1, 1) {
                if (p[u].FI == 0) break;
                int id = p[u].SE;
                u = p[u].FI;
                ans = ans * qry(pre[u], id, i) % l;
                ans = ans * qry(id + 1, pst[u], i) % l;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

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

Compilation message

sprinkler.cpp: In function 'void dfs(int)':
sprinkler.cpp:13: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]
   13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   48 |     REP (i, 0, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
sprinkler.cpp:48:5: note: in expansion of macro 'REP'
   48 |     REP (i, 0, adj[u].size()) {
      |     ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 136460 KB Output is correct
2 Correct 71 ms 136460 KB Output is correct
3 Correct 69 ms 136440 KB Output is correct
4 Correct 76 ms 136664 KB Output is correct
5 Correct 77 ms 136556 KB Output is correct
6 Correct 70 ms 136580 KB Output is correct
7 Correct 69 ms 136524 KB Output is correct
8 Correct 70 ms 136580 KB Output is correct
9 Correct 70 ms 136528 KB Output is correct
10 Correct 79 ms 136456 KB Output is correct
11 Correct 69 ms 136480 KB Output is correct
12 Correct 70 ms 136432 KB Output is correct
13 Correct 69 ms 136580 KB Output is correct
14 Correct 68 ms 136452 KB Output is correct
15 Correct 70 ms 136492 KB Output is correct
16 Correct 71 ms 136492 KB Output is correct
17 Correct 68 ms 136484 KB Output is correct
18 Correct 70 ms 136476 KB Output is correct
19 Correct 73 ms 136516 KB Output is correct
20 Correct 68 ms 136480 KB Output is correct
21 Correct 69 ms 136536 KB Output is correct
22 Correct 72 ms 136524 KB Output is correct
23 Correct 69 ms 136420 KB Output is correct
24 Correct 67 ms 136500 KB Output is correct
25 Correct 70 ms 136488 KB Output is correct
26 Correct 70 ms 136524 KB Output is correct
27 Correct 72 ms 136424 KB Output is correct
28 Correct 73 ms 136540 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 136448 KB Output is correct
2 Runtime error 102 ms 25468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 136448 KB Output is correct
2 Runtime error 102 ms 25468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 136448 KB Output is correct
2 Correct 2029 ms 156628 KB Output is correct
3 Execution timed out 4098 ms 153560 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 136512 KB Output is correct
2 Correct 2016 ms 156284 KB Output is correct
3 Execution timed out 4083 ms 151716 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 136460 KB Output is correct
2 Correct 71 ms 136460 KB Output is correct
3 Correct 69 ms 136440 KB Output is correct
4 Correct 76 ms 136664 KB Output is correct
5 Correct 77 ms 136556 KB Output is correct
6 Correct 70 ms 136580 KB Output is correct
7 Correct 69 ms 136524 KB Output is correct
8 Correct 70 ms 136580 KB Output is correct
9 Correct 70 ms 136528 KB Output is correct
10 Correct 79 ms 136456 KB Output is correct
11 Correct 69 ms 136480 KB Output is correct
12 Correct 70 ms 136432 KB Output is correct
13 Correct 69 ms 136580 KB Output is correct
14 Correct 68 ms 136452 KB Output is correct
15 Correct 70 ms 136492 KB Output is correct
16 Correct 71 ms 136492 KB Output is correct
17 Correct 68 ms 136484 KB Output is correct
18 Correct 70 ms 136476 KB Output is correct
19 Correct 73 ms 136516 KB Output is correct
20 Correct 68 ms 136480 KB Output is correct
21 Correct 69 ms 136536 KB Output is correct
22 Correct 72 ms 136524 KB Output is correct
23 Correct 69 ms 136420 KB Output is correct
24 Correct 67 ms 136500 KB Output is correct
25 Correct 70 ms 136488 KB Output is correct
26 Correct 70 ms 136524 KB Output is correct
27 Correct 72 ms 136424 KB Output is correct
28 Correct 73 ms 136540 KB Output is correct
29 Correct 72 ms 136448 KB Output is correct
30 Runtime error 102 ms 25468 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -