oj.uz

Submission #875787

# Submission time Handle Problem Language Result Execution time Memory
875787 2023-11-20T13:46:25 Z danikoynov Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 74964 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxq = 4e5 + 10;

struct query
{
    int type, ver, d, t;
    ll w;
} ask[maxq];

const int maxn = 2e5 + 10;

int n, q;
ll l, h[maxn];
vector < query > task[maxn];
vector < int > adj[maxn];

bool cmp(query a1, query a2)
{
    return a1.d < a2.d;
}

void input()
{
    cin >> n >> l;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i ++)
        cin >> h[i];
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        cin >> ask[i].type;
        if (ask[i].type == 1)
            cin >> ask[i].ver >> ask[i].d >> ask[i].w;
        else
            cin >> ask[i].ver;
        ask[i].t = i;
    }
}


struct segment_tree
{
    vector < ll > tree, lazy;

    segment_tree(int len = 0)
    {
        tree.resize(4 * (len + 1));
        lazy.resize(4 * (len + 1));
        fill(tree.begin(), tree.end(), 1);
        fill(lazy.begin(), lazy.end(), 1);
    }

    void push_lazy(int root, int left, int right)
    {
        tree[root] *= lazy[root];
        tree[root] %= l;
        if (left != right)
        {
            lazy[root * 2] *= (lazy[root]);
            lazy[root * 2 + 1] *= (lazy[root]);
            lazy[root * 2] %= l;
            lazy[root * 2 + 1] %= l;
        }

        lazy[root] = 1;
    }

    void update_range(int root, int left, int right, int qleft, int qright, ll val)
    {
        //cout << "update range " << root << " " << left << " " << right << " " << qleft << " " << qright << endl;
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    ll get_point(int root, int left, int right, int pos)
    {
        push_lazy(root, left, right);
        if (left == right)
            return tree[root];

        int mid = (left + right) / 2;
        if (pos <= mid)
            return get_point(root * 2, left, mid, pos);
        return get_point(root * 2 + 1, mid + 1, right, pos);
    }
};

segment_tree st;
int par[maxn], depth[maxn], offset[maxn];
vector < int > by_depth[maxn];
int tin[maxn], tout[maxn], timer, rev[maxn];
void dfs(int v)
{
    tin[v] = ++ timer;
    ///cout << "dfs " << v << " "  << depth[v] << endl;
    rev[v] = by_depth[depth[v]].size();
    by_depth[depth[v]].push_back(v);
    for (int u : adj[v])
    {
        if (u == par[v])
            continue;
        par[u] = v;
        depth[u] = depth[v] + 1;
        dfs(u);
    }
    tout[v] = timer;
}

const int maxd = 40;

void update_row(int row, int left, int right, ll val)
{

    int lf = 0, rf = (int)(by_depth[row].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tin[by_depth[row][mf]] < left)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    int lb = lf;

    lf = 0;
    rf = (int)(by_depth[row].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tin[by_depth[row][mf]] <= right)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    int rb = rf;
    ///cout << "here " << row << " " << lb << " " << rb << endl;
    st.update_range(1, 0, n - 1,
                    offset[row] + lb, offset[row] + rb, val);

    /**for (int cur : by_depth[row])
    { ///cout << "vertex " << cur << endl;
        if (tin[cur] >= lf && tin[cur] <= rf)
            h[cur] = (h[cur] * val) % l;
    }*/
}

void make_query(int v)
{
    ll ans = h[v];
    ans = ans * st.get_point(1, 0, n - 1,
                             offset[depth[v]] + rev[v]);
                            //cout << v << " :: " << offset[depth[v]] + rev[v] << endl;
    ans %= l;
    cout << ans << endl;
}
void simulate()
{
    st = segment_tree(n);
    for (int i = 1; i <= n; i ++)
    {
        offset[i] = offset[i - 1] + by_depth[i - 1].size();
        ///cout << i << " : " << offset[i] << endl;
    }
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == 2)
            make_query(ask[i].ver);
        else
        {
            int cnt = 0, ver = ask[i].ver;
            while(ver != 1 && cnt <= ask[i].d)
            {
                int lf = ask[i].d - cnt;
                update_row(depth[ver] + lf, tin[ver], tout[ver], ask[i].w);
                ///cout << "update " << ver << " " << depth[ver] + lf << endl;
                //if (lf != 0)
                update_row(depth[ver] + lf - 1, tin[ver], tout[ver], ask[i].w);
                cnt ++;
                ver = par[ver];
            }
            if (ver == 1 && cnt <= ask[i].d)
            {
                int lf = ask[i].d - cnt;
                for (int j = 0; j <= lf; j ++)
                {
                    ///cout << "update " << ver << " " << depth[ver] + j << endl;
                    update_row(depth[ver] + j, tin[ver], tout[ver], ask[i].w);
                }
            }
            /**for (int i = 1; i <= n; i ++)
                        cout << h[i] << " ";
                    cout << endl;*/
        }

    }

}
void solve()
{
    input();
    ///offline_queries();
    depth[1] = 1;
    dfs(1);
    simulate();
}

int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 11 ms 19036 KB Output is correct
5 Correct 10 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 7 ms 19036 KB Output is correct
8 Correct 5 ms 19036 KB Output is correct
9 Correct 4 ms 18876 KB Output is correct
10 Correct 5 ms 19188 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 5 ms 18936 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 18780 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 4 ms 18948 KB Output is correct
21 Correct 4 ms 18780 KB Output is correct
22 Correct 5 ms 18780 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 3 ms 18780 KB Output is correct
25 Correct 4 ms 18780 KB Output is correct
26 Correct 5 ms 18780 KB Output is correct
27 Correct 5 ms 18780 KB Output is correct
28 Correct 5 ms 18776 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18928 KB Output is correct
2 Correct 424 ms 58532 KB Output is correct
3 Correct 1196 ms 57128 KB Output is correct
4 Correct 677 ms 68380 KB Output is correct
5 Correct 671 ms 57572 KB Output is correct
6 Correct 766 ms 57320 KB Output is correct
7 Correct 748 ms 57920 KB Output is correct
8 Correct 564 ms 58008 KB Output is correct
9 Correct 476 ms 74964 KB Output is correct
10 Correct 1040 ms 72768 KB Output is correct
11 Correct 399 ms 58404 KB Output is correct
12 Correct 1217 ms 57004 KB Output is correct
13 Correct 1094 ms 58232 KB Output is correct
14 Correct 1264 ms 57652 KB Output is correct
15 Correct 1175 ms 57148 KB Output is correct
16 Correct 1141 ms 57604 KB Output is correct
17 Correct 1223 ms 57748 KB Output is correct
18 Correct 4 ms 18776 KB Output is correct
19 Correct 4 ms 18776 KB Output is correct
20 Correct 5 ms 18780 KB Output is correct
21 Correct 5 ms 18780 KB Output is correct
22 Correct 4 ms 18872 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18928 KB Output is correct
2 Correct 424 ms 58532 KB Output is correct
3 Correct 1196 ms 57128 KB Output is correct
4 Correct 677 ms 68380 KB Output is correct
5 Correct 671 ms 57572 KB Output is correct
6 Correct 766 ms 57320 KB Output is correct
7 Correct 748 ms 57920 KB Output is correct
8 Correct 564 ms 58008 KB Output is correct
9 Correct 476 ms 74964 KB Output is correct
10 Correct 1040 ms 72768 KB Output is correct
11 Correct 399 ms 58404 KB Output is correct
12 Correct 1217 ms 57004 KB Output is correct
13 Correct 1094 ms 58232 KB Output is correct
14 Correct 1264 ms 57652 KB Output is correct
15 Correct 1175 ms 57148 KB Output is correct
16 Correct 1141 ms 57604 KB Output is correct
17 Correct 1223 ms 57748 KB Output is correct
18 Correct 4 ms 18776 KB Output is correct
19 Correct 4 ms 18776 KB Output is correct
20 Correct 5 ms 18780 KB Output is correct
21 Correct 5 ms 18780 KB Output is correct
22 Correct 4 ms 18872 KB Output is correct
23 Correct 4 ms 18776 KB Output is correct
24 Correct 467 ms 58196 KB Output is correct
25 Correct 1663 ms 56816 KB Output is correct
26 Correct 764 ms 73748 KB Output is correct
27 Correct 861 ms 57492 KB Output is correct
28 Correct 845 ms 57692 KB Output is correct
29 Correct 897 ms 57248 KB Output is correct
30 Correct 638 ms 58012 KB Output is correct
31 Correct 542 ms 69596 KB Output is correct
32 Correct 1422 ms 72204 KB Output is correct
33 Correct 501 ms 58000 KB Output is correct
34 Correct 1701 ms 56868 KB Output is correct
35 Correct 4 ms 18780 KB Output is correct
36 Correct 4 ms 18780 KB Output is correct
37 Correct 5 ms 18780 KB Output is correct
38 Correct 4 ms 18780 KB Output is correct
39 Correct 4 ms 18780 KB Output is correct
40 Correct 4 ms 18780 KB Output is correct
41 Correct 4 ms 18780 KB Output is correct
42 Correct 4 ms 18780 KB Output is correct
43 Correct 4 ms 18780 KB Output is correct
44 Correct 4 ms 18780 KB Output is correct
45 Correct 4 ms 18780 KB Output is correct
46 Correct 5 ms 18780 KB Output is correct
47 Correct 4 ms 18776 KB Output is correct
48 Correct 4 ms 18872 KB Output is correct
49 Correct 4 ms 18780 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 2128 ms 72024 KB Output is correct
3 Execution timed out 4043 ms 67924 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 1924 ms 69016 KB Output is correct
3 Execution timed out 4054 ms 63784 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 11 ms 19036 KB Output is correct
5 Correct 10 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 7 ms 19036 KB Output is correct
8 Correct 5 ms 19036 KB Output is correct
9 Correct 4 ms 18876 KB Output is correct
10 Correct 5 ms 19188 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 5 ms 18936 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 18780 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 4 ms 18948 KB Output is correct
21 Correct 4 ms 18780 KB Output is correct
22 Correct 5 ms 18780 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 3 ms 18780 KB Output is correct
25 Correct 4 ms 18780 KB Output is correct
26 Correct 5 ms 18780 KB Output is correct
27 Correct 5 ms 18780 KB Output is correct
28 Correct 5 ms 18776 KB Output is correct
29 Correct 3 ms 18928 KB Output is correct
30 Correct 424 ms 58532 KB Output is correct
31 Correct 1196 ms 57128 KB Output is correct
32 Correct 677 ms 68380 KB Output is correct
33 Correct 671 ms 57572 KB Output is correct
34 Correct 766 ms 57320 KB Output is correct
35 Correct 748 ms 57920 KB Output is correct
36 Correct 564 ms 58008 KB Output is correct
37 Correct 476 ms 74964 KB Output is correct
38 Correct 1040 ms 72768 KB Output is correct
39 Correct 399 ms 58404 KB Output is correct
40 Correct 1217 ms 57004 KB Output is correct
41 Correct 1094 ms 58232 KB Output is correct
42 Correct 1264 ms 57652 KB Output is correct
43 Correct 1175 ms 57148 KB Output is correct
44 Correct 1141 ms 57604 KB Output is correct
45 Correct 1223 ms 57748 KB Output is correct
46 Correct 4 ms 18776 KB Output is correct
47 Correct 4 ms 18776 KB Output is correct
48 Correct 5 ms 18780 KB Output is correct
49 Correct 5 ms 18780 KB Output is correct
50 Correct 4 ms 18872 KB Output is correct
51 Correct 4 ms 18776 KB Output is correct
52 Correct 467 ms 58196 KB Output is correct
53 Correct 1663 ms 56816 KB Output is correct
54 Correct 764 ms 73748 KB Output is correct
55 Correct 861 ms 57492 KB Output is correct
56 Correct 845 ms 57692 KB Output is correct
57 Correct 897 ms 57248 KB Output is correct
58 Correct 638 ms 58012 KB Output is correct
59 Correct 542 ms 69596 KB Output is correct
60 Correct 1422 ms 72204 KB Output is correct
61 Correct 501 ms 58000 KB Output is correct
62 Correct 1701 ms 56868 KB Output is correct
63 Correct 4 ms 18780 KB Output is correct
64 Correct 4 ms 18780 KB Output is correct
65 Correct 5 ms 18780 KB Output is correct
66 Correct 4 ms 18780 KB Output is correct
67 Correct 4 ms 18780 KB Output is correct
68 Correct 4 ms 18780 KB Output is correct
69 Correct 4 ms 18780 KB Output is correct
70 Correct 4 ms 18780 KB Output is correct
71 Correct 4 ms 18780 KB Output is correct
72 Correct 4 ms 18780 KB Output is correct
73 Correct 4 ms 18780 KB Output is correct
74 Correct 5 ms 18780 KB Output is correct
75 Correct 4 ms 18776 KB Output is correct
76 Correct 4 ms 18872 KB Output is correct
77 Correct 4 ms 18780 KB Output is correct
78 Correct 4 ms 18776 KB Output is correct
79 Correct 2128 ms 72024 KB Output is correct
80 Execution timed out 4043 ms 67924 KB Time limit exceeded
81 Halted 0 ms 0 KB -