oj.uz

Submission #568231

# Submission time Handle Problem Language Result Execution time Memory
568231 2022-05-25T02:11:11 Z maomao90 Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 295984 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;

#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 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;
                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;
                incre(id, i, w);
            }
        } else {
            int x; cin >> x;
            int ans = h[x];
            ans = (ll) 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 = (ll) ans * qry(pre[u], id, i) % l;
                ans = (ll) 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: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++)
......
   51 |     REP (i, 0, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
sprinkler.cpp:51:5: note: in expansion of macro 'REP'
   51 |     REP (i, 0, adj[u].size()) {
      |     ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 272696 KB Output is correct
2 Correct 110 ms 272688 KB Output is correct
3 Correct 105 ms 272628 KB Output is correct
4 Correct 110 ms 272760 KB Output is correct
5 Correct 118 ms 272740 KB Output is correct
6 Correct 112 ms 272724 KB Output is correct
7 Correct 107 ms 272724 KB Output is correct
8 Correct 107 ms 272844 KB Output is correct
9 Correct 106 ms 272716 KB Output is correct
10 Correct 109 ms 272688 KB Output is correct
11 Correct 106 ms 272772 KB Output is correct
12 Correct 105 ms 272652 KB Output is correct
13 Correct 106 ms 272712 KB Output is correct
14 Correct 108 ms 272792 KB Output is correct
15 Correct 107 ms 272652 KB Output is correct
16 Correct 105 ms 272660 KB Output is correct
17 Correct 105 ms 272676 KB Output is correct
18 Correct 108 ms 272672 KB Output is correct
19 Correct 108 ms 272736 KB Output is correct
20 Correct 104 ms 272744 KB Output is correct
21 Correct 105 ms 272700 KB Output is correct
22 Correct 106 ms 272716 KB Output is correct
23 Correct 120 ms 272692 KB Output is correct
24 Correct 105 ms 272724 KB Output is correct
25 Correct 104 ms 272656 KB Output is correct
26 Correct 108 ms 272656 KB Output is correct
27 Correct 110 ms 272656 KB Output is correct
28 Correct 103 ms 272636 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 272736 KB Output is correct
2 Correct 1423 ms 290972 KB Output is correct
3 Correct 939 ms 287664 KB Output is correct
4 Correct 813 ms 291016 KB Output is correct
5 Correct 1155 ms 289352 KB Output is correct
6 Correct 992 ms 290724 KB Output is correct
7 Correct 989 ms 291920 KB Output is correct
8 Correct 734 ms 295984 KB Output is correct
9 Correct 762 ms 295464 KB Output is correct
10 Correct 854 ms 291656 KB Output is correct
11 Correct 1358 ms 291164 KB Output is correct
12 Correct 1000 ms 287708 KB Output is correct
13 Correct 667 ms 293260 KB Output is correct
14 Correct 703 ms 293320 KB Output is correct
15 Correct 706 ms 293152 KB Output is correct
16 Correct 686 ms 293252 KB Output is correct
17 Correct 790 ms 293640 KB Output is correct
18 Correct 108 ms 272672 KB Output is correct
19 Correct 109 ms 272748 KB Output is correct
20 Correct 117 ms 272720 KB Output is correct
21 Correct 104 ms 272652 KB Output is correct
22 Correct 109 ms 272736 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 272736 KB Output is correct
2 Correct 1423 ms 290972 KB Output is correct
3 Correct 939 ms 287664 KB Output is correct
4 Correct 813 ms 291016 KB Output is correct
5 Correct 1155 ms 289352 KB Output is correct
6 Correct 992 ms 290724 KB Output is correct
7 Correct 989 ms 291920 KB Output is correct
8 Correct 734 ms 295984 KB Output is correct
9 Correct 762 ms 295464 KB Output is correct
10 Correct 854 ms 291656 KB Output is correct
11 Correct 1358 ms 291164 KB Output is correct
12 Correct 1000 ms 287708 KB Output is correct
13 Correct 667 ms 293260 KB Output is correct
14 Correct 703 ms 293320 KB Output is correct
15 Correct 706 ms 293152 KB Output is correct
16 Correct 686 ms 293252 KB Output is correct
17 Correct 790 ms 293640 KB Output is correct
18 Correct 108 ms 272672 KB Output is correct
19 Correct 109 ms 272748 KB Output is correct
20 Correct 117 ms 272720 KB Output is correct
21 Correct 104 ms 272652 KB Output is correct
22 Correct 109 ms 272736 KB Output is correct
23 Correct 112 ms 272652 KB Output is correct
24 Correct 1429 ms 290908 KB Output is correct
25 Correct 1128 ms 287680 KB Output is correct
26 Correct 801 ms 293580 KB Output is correct
27 Correct 1198 ms 289256 KB Output is correct
28 Correct 1106 ms 290836 KB Output is correct
29 Correct 1080 ms 291744 KB Output is correct
30 Correct 804 ms 295756 KB Output is correct
31 Correct 709 ms 292900 KB Output is correct
32 Correct 1117 ms 291916 KB Output is correct
33 Correct 1384 ms 291092 KB Output is correct
34 Correct 1151 ms 287640 KB Output is correct
35 Correct 107 ms 272716 KB Output is correct
36 Correct 105 ms 272680 KB Output is correct
37 Correct 107 ms 272712 KB Output is correct
38 Correct 105 ms 272720 KB Output is correct
39 Correct 110 ms 272640 KB Output is correct
40 Correct 105 ms 272656 KB Output is correct
41 Correct 107 ms 272716 KB Output is correct
42 Correct 109 ms 272680 KB Output is correct
43 Correct 108 ms 272684 KB Output is correct
44 Correct 110 ms 272808 KB Output is correct
45 Correct 107 ms 272692 KB Output is correct
46 Correct 106 ms 272692 KB Output is correct
47 Correct 105 ms 272680 KB Output is correct
48 Correct 110 ms 272688 KB Output is correct
49 Correct 106 ms 272708 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 272700 KB Output is correct
2 Correct 2175 ms 292976 KB Output is correct
3 Execution timed out 4067 ms 289840 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 272716 KB Output is correct
2 Correct 2153 ms 292452 KB Output is correct
3 Execution timed out 4082 ms 287948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 272696 KB Output is correct
2 Correct 110 ms 272688 KB Output is correct
3 Correct 105 ms 272628 KB Output is correct
4 Correct 110 ms 272760 KB Output is correct
5 Correct 118 ms 272740 KB Output is correct
6 Correct 112 ms 272724 KB Output is correct
7 Correct 107 ms 272724 KB Output is correct
8 Correct 107 ms 272844 KB Output is correct
9 Correct 106 ms 272716 KB Output is correct
10 Correct 109 ms 272688 KB Output is correct
11 Correct 106 ms 272772 KB Output is correct
12 Correct 105 ms 272652 KB Output is correct
13 Correct 106 ms 272712 KB Output is correct
14 Correct 108 ms 272792 KB Output is correct
15 Correct 107 ms 272652 KB Output is correct
16 Correct 105 ms 272660 KB Output is correct
17 Correct 105 ms 272676 KB Output is correct
18 Correct 108 ms 272672 KB Output is correct
19 Correct 108 ms 272736 KB Output is correct
20 Correct 104 ms 272744 KB Output is correct
21 Correct 105 ms 272700 KB Output is correct
22 Correct 106 ms 272716 KB Output is correct
23 Correct 120 ms 272692 KB Output is correct
24 Correct 105 ms 272724 KB Output is correct
25 Correct 104 ms 272656 KB Output is correct
26 Correct 108 ms 272656 KB Output is correct
27 Correct 110 ms 272656 KB Output is correct
28 Correct 103 ms 272636 KB Output is correct
29 Correct 103 ms 272736 KB Output is correct
30 Correct 1423 ms 290972 KB Output is correct
31 Correct 939 ms 287664 KB Output is correct
32 Correct 813 ms 291016 KB Output is correct
33 Correct 1155 ms 289352 KB Output is correct
34 Correct 992 ms 290724 KB Output is correct
35 Correct 989 ms 291920 KB Output is correct
36 Correct 734 ms 295984 KB Output is correct
37 Correct 762 ms 295464 KB Output is correct
38 Correct 854 ms 291656 KB Output is correct
39 Correct 1358 ms 291164 KB Output is correct
40 Correct 1000 ms 287708 KB Output is correct
41 Correct 667 ms 293260 KB Output is correct
42 Correct 703 ms 293320 KB Output is correct
43 Correct 706 ms 293152 KB Output is correct
44 Correct 686 ms 293252 KB Output is correct
45 Correct 790 ms 293640 KB Output is correct
46 Correct 108 ms 272672 KB Output is correct
47 Correct 109 ms 272748 KB Output is correct
48 Correct 117 ms 272720 KB Output is correct
49 Correct 104 ms 272652 KB Output is correct
50 Correct 109 ms 272736 KB Output is correct
51 Correct 112 ms 272652 KB Output is correct
52 Correct 1429 ms 290908 KB Output is correct
53 Correct 1128 ms 287680 KB Output is correct
54 Correct 801 ms 293580 KB Output is correct
55 Correct 1198 ms 289256 KB Output is correct
56 Correct 1106 ms 290836 KB Output is correct
57 Correct 1080 ms 291744 KB Output is correct
58 Correct 804 ms 295756 KB Output is correct
59 Correct 709 ms 292900 KB Output is correct
60 Correct 1117 ms 291916 KB Output is correct
61 Correct 1384 ms 291092 KB Output is correct
62 Correct 1151 ms 287640 KB Output is correct
63 Correct 107 ms 272716 KB Output is correct
64 Correct 105 ms 272680 KB Output is correct
65 Correct 107 ms 272712 KB Output is correct
66 Correct 105 ms 272720 KB Output is correct
67 Correct 110 ms 272640 KB Output is correct
68 Correct 105 ms 272656 KB Output is correct
69 Correct 107 ms 272716 KB Output is correct
70 Correct 109 ms 272680 KB Output is correct
71 Correct 108 ms 272684 KB Output is correct
72 Correct 110 ms 272808 KB Output is correct
73 Correct 107 ms 272692 KB Output is correct
74 Correct 106 ms 272692 KB Output is correct
75 Correct 105 ms 272680 KB Output is correct
76 Correct 110 ms 272688 KB Output is correct
77 Correct 106 ms 272708 KB Output is correct
78 Correct 107 ms 272700 KB Output is correct
79 Correct 2175 ms 292976 KB Output is correct
80 Execution timed out 4067 ms 289840 KB Time limit exceeded
81 Halted 0 ms 0 KB -