oj.uz

Submission #875789

# Submission time Handle Problem Language Result Execution time Memory
875789 2023-11-20T13:48:38 Z danikoynov Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 70736 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;
    }
}


ll tree[4 * maxn], lazy[4 * maxn];


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);
}


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;
    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 * 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()
{

    for (int i = 0; i <= 4 * n; i ++)
        tree[i] = 1, lazy[i] = 1;
    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 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20928 KB Output is correct
4 Correct 11 ms 21140 KB Output is correct
5 Correct 10 ms 21084 KB Output is correct
6 Correct 7 ms 21084 KB Output is correct
7 Correct 7 ms 21084 KB Output is correct
8 Correct 5 ms 21084 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 5 ms 20828 KB Output is correct
11 Correct 5 ms 20828 KB Output is correct
12 Correct 5 ms 20828 KB Output is correct
13 Correct 4 ms 20828 KB Output is correct
14 Correct 4 ms 21016 KB Output is correct
15 Correct 5 ms 21016 KB Output is correct
16 Correct 5 ms 20940 KB Output is correct
17 Correct 4 ms 20828 KB Output is correct
18 Correct 5 ms 20828 KB Output is correct
19 Correct 5 ms 20828 KB Output is correct
20 Correct 4 ms 20828 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 4 ms 20824 KB Output is correct
23 Correct 4 ms 20828 KB Output is correct
24 Correct 4 ms 20824 KB Output is correct
25 Correct 4 ms 20824 KB Output is correct
26 Correct 4 ms 20824 KB Output is correct
27 Correct 4 ms 20824 KB Output is correct
28 Correct 4 ms 20828 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 384 ms 53816 KB Output is correct
3 Correct 1191 ms 50696 KB Output is correct
4 Correct 644 ms 63028 KB Output is correct
5 Correct 627 ms 52128 KB Output is correct
6 Correct 734 ms 52304 KB Output is correct
7 Correct 730 ms 52688 KB Output is correct
8 Correct 548 ms 52552 KB Output is correct
9 Correct 406 ms 70736 KB Output is correct
10 Correct 1052 ms 65900 KB Output is correct
11 Correct 393 ms 53796 KB Output is correct
12 Correct 1095 ms 50512 KB Output is correct
13 Correct 1062 ms 51908 KB Output is correct
14 Correct 1158 ms 51140 KB Output is correct
15 Correct 1146 ms 51028 KB Output is correct
16 Correct 1102 ms 51028 KB Output is correct
17 Correct 1185 ms 51416 KB Output is correct
18 Correct 4 ms 20824 KB Output is correct
19 Correct 4 ms 20828 KB Output is correct
20 Correct 4 ms 20828 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 5 ms 20828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 384 ms 53816 KB Output is correct
3 Correct 1191 ms 50696 KB Output is correct
4 Correct 644 ms 63028 KB Output is correct
5 Correct 627 ms 52128 KB Output is correct
6 Correct 734 ms 52304 KB Output is correct
7 Correct 730 ms 52688 KB Output is correct
8 Correct 548 ms 52552 KB Output is correct
9 Correct 406 ms 70736 KB Output is correct
10 Correct 1052 ms 65900 KB Output is correct
11 Correct 393 ms 53796 KB Output is correct
12 Correct 1095 ms 50512 KB Output is correct
13 Correct 1062 ms 51908 KB Output is correct
14 Correct 1158 ms 51140 KB Output is correct
15 Correct 1146 ms 51028 KB Output is correct
16 Correct 1102 ms 51028 KB Output is correct
17 Correct 1185 ms 51416 KB Output is correct
18 Correct 4 ms 20824 KB Output is correct
19 Correct 4 ms 20828 KB Output is correct
20 Correct 4 ms 20828 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 5 ms 20828 KB Output is correct
23 Correct 4 ms 20828 KB Output is correct
24 Correct 471 ms 53720 KB Output is correct
25 Correct 1548 ms 50512 KB Output is correct
26 Correct 726 ms 68208 KB Output is correct
27 Correct 746 ms 52120 KB Output is correct
28 Correct 893 ms 52560 KB Output is correct
29 Correct 865 ms 52048 KB Output is correct
30 Correct 617 ms 52712 KB Output is correct
31 Correct 475 ms 65188 KB Output is correct
32 Correct 1375 ms 66124 KB Output is correct
33 Correct 436 ms 53700 KB Output is correct
34 Correct 1557 ms 50928 KB Output is correct
35 Correct 4 ms 20824 KB Output is correct
36 Correct 4 ms 20824 KB Output is correct
37 Correct 5 ms 20828 KB Output is correct
38 Correct 4 ms 20828 KB Output is correct
39 Correct 4 ms 20828 KB Output is correct
40 Correct 4 ms 20828 KB Output is correct
41 Correct 4 ms 20828 KB Output is correct
42 Correct 5 ms 20828 KB Output is correct
43 Correct 4 ms 20828 KB Output is correct
44 Correct 4 ms 21084 KB Output is correct
45 Correct 4 ms 20828 KB Output is correct
46 Correct 4 ms 20828 KB Output is correct
47 Correct 5 ms 20828 KB Output is correct
48 Correct 4 ms 20828 KB Output is correct
49 Correct 4 ms 20828 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20920 KB Output is correct
2 Correct 1900 ms 68160 KB Output is correct
3 Execution timed out 4059 ms 62796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 1896 ms 64572 KB Output is correct
3 Execution timed out 4101 ms 58688 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 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20928 KB Output is correct
4 Correct 11 ms 21140 KB Output is correct
5 Correct 10 ms 21084 KB Output is correct
6 Correct 7 ms 21084 KB Output is correct
7 Correct 7 ms 21084 KB Output is correct
8 Correct 5 ms 21084 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 5 ms 20828 KB Output is correct
11 Correct 5 ms 20828 KB Output is correct
12 Correct 5 ms 20828 KB Output is correct
13 Correct 4 ms 20828 KB Output is correct
14 Correct 4 ms 21016 KB Output is correct
15 Correct 5 ms 21016 KB Output is correct
16 Correct 5 ms 20940 KB Output is correct
17 Correct 4 ms 20828 KB Output is correct
18 Correct 5 ms 20828 KB Output is correct
19 Correct 5 ms 20828 KB Output is correct
20 Correct 4 ms 20828 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 4 ms 20824 KB Output is correct
23 Correct 4 ms 20828 KB Output is correct
24 Correct 4 ms 20824 KB Output is correct
25 Correct 4 ms 20824 KB Output is correct
26 Correct 4 ms 20824 KB Output is correct
27 Correct 4 ms 20824 KB Output is correct
28 Correct 4 ms 20828 KB Output is correct
29 Correct 4 ms 20828 KB Output is correct
30 Correct 384 ms 53816 KB Output is correct
31 Correct 1191 ms 50696 KB Output is correct
32 Correct 644 ms 63028 KB Output is correct
33 Correct 627 ms 52128 KB Output is correct
34 Correct 734 ms 52304 KB Output is correct
35 Correct 730 ms 52688 KB Output is correct
36 Correct 548 ms 52552 KB Output is correct
37 Correct 406 ms 70736 KB Output is correct
38 Correct 1052 ms 65900 KB Output is correct
39 Correct 393 ms 53796 KB Output is correct
40 Correct 1095 ms 50512 KB Output is correct
41 Correct 1062 ms 51908 KB Output is correct
42 Correct 1158 ms 51140 KB Output is correct
43 Correct 1146 ms 51028 KB Output is correct
44 Correct 1102 ms 51028 KB Output is correct
45 Correct 1185 ms 51416 KB Output is correct
46 Correct 4 ms 20824 KB Output is correct
47 Correct 4 ms 20828 KB Output is correct
48 Correct 4 ms 20828 KB Output is correct
49 Correct 4 ms 20828 KB Output is correct
50 Correct 5 ms 20828 KB Output is correct
51 Correct 4 ms 20828 KB Output is correct
52 Correct 471 ms 53720 KB Output is correct
53 Correct 1548 ms 50512 KB Output is correct
54 Correct 726 ms 68208 KB Output is correct
55 Correct 746 ms 52120 KB Output is correct
56 Correct 893 ms 52560 KB Output is correct
57 Correct 865 ms 52048 KB Output is correct
58 Correct 617 ms 52712 KB Output is correct
59 Correct 475 ms 65188 KB Output is correct
60 Correct 1375 ms 66124 KB Output is correct
61 Correct 436 ms 53700 KB Output is correct
62 Correct 1557 ms 50928 KB Output is correct
63 Correct 4 ms 20824 KB Output is correct
64 Correct 4 ms 20824 KB Output is correct
65 Correct 5 ms 20828 KB Output is correct
66 Correct 4 ms 20828 KB Output is correct
67 Correct 4 ms 20828 KB Output is correct
68 Correct 4 ms 20828 KB Output is correct
69 Correct 4 ms 20828 KB Output is correct
70 Correct 5 ms 20828 KB Output is correct
71 Correct 4 ms 20828 KB Output is correct
72 Correct 4 ms 21084 KB Output is correct
73 Correct 4 ms 20828 KB Output is correct
74 Correct 4 ms 20828 KB Output is correct
75 Correct 5 ms 20828 KB Output is correct
76 Correct 4 ms 20828 KB Output is correct
77 Correct 4 ms 20828 KB Output is correct
78 Correct 4 ms 20920 KB Output is correct
79 Correct 1900 ms 68160 KB Output is correct
80 Execution timed out 4059 ms 62796 KB Time limit exceeded
81 Halted 0 ms 0 KB -