oj.uz

Submission #875778

# Submission time Handle Problem Language Result Execution time Memory
875778 2023-11-20T13:16:22 Z danikoynov Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 58392 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;
    }
}



int par[maxn], depth[maxn];
vector < int > by_depth[maxn];
int tin[maxn], tout[maxn], timer;
void dfs(int v)
{
    tin[v] = ++ timer;
    ///cout << "dfs " << v << " "  << depth[v] << endl;
    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 lf, int rf, ll 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 simulate()
{
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == 2)
            cout << h[ask[i].ver] << endl;
        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 3 ms 20824 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20824 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 6 ms 20828 KB Output is correct
6 Correct 7 ms 20828 KB Output is correct
7 Correct 8 ms 20992 KB Output is correct
8 Correct 8 ms 20828 KB Output is correct
9 Correct 4 ms 20992 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20924 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 4 ms 20828 KB Output is correct
14 Correct 4 ms 20828 KB Output is correct
15 Correct 4 ms 20828 KB Output is correct
16 Correct 4 ms 20828 KB Output is correct
17 Correct 4 ms 20828 KB Output is correct
18 Correct 4 ms 20940 KB Output is correct
19 Correct 4 ms 20828 KB Output is correct
20 Correct 4 ms 21080 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 4 ms 20828 KB Output is correct
23 Correct 4 ms 20828 KB Output is correct
24 Correct 4 ms 20992 KB Output is correct
25 Correct 4 ms 20828 KB Output is correct
26 Correct 4 ms 20828 KB Output is correct
27 Correct 4 ms 21000 KB Output is correct
28 Correct 4 ms 20824 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 219 ms 39596 KB Output is correct
3 Correct 1030 ms 36768 KB Output is correct
4 Correct 240 ms 48720 KB Output is correct
5 Correct 469 ms 38228 KB Output is correct
6 Execution timed out 4026 ms 36944 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 219 ms 39596 KB Output is correct
3 Correct 1030 ms 36768 KB Output is correct
4 Correct 240 ms 48720 KB Output is correct
5 Correct 469 ms 38228 KB Output is correct
6 Execution timed out 4026 ms 36944 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 238 ms 53468 KB Output is correct
3 Correct 517 ms 57936 KB Output is correct
4 Correct 295 ms 58392 KB Output is correct
5 Execution timed out 4054 ms 45640 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 247 ms 50160 KB Output is correct
3 Correct 555 ms 54172 KB Output is correct
4 Correct 333 ms 56500 KB Output is correct
5 Correct 3678 ms 46888 KB Output is correct
6 Execution timed out 4006 ms 45136 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20824 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 6 ms 20828 KB Output is correct
6 Correct 7 ms 20828 KB Output is correct
7 Correct 8 ms 20992 KB Output is correct
8 Correct 8 ms 20828 KB Output is correct
9 Correct 4 ms 20992 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20924 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 4 ms 20828 KB Output is correct
14 Correct 4 ms 20828 KB Output is correct
15 Correct 4 ms 20828 KB Output is correct
16 Correct 4 ms 20828 KB Output is correct
17 Correct 4 ms 20828 KB Output is correct
18 Correct 4 ms 20940 KB Output is correct
19 Correct 4 ms 20828 KB Output is correct
20 Correct 4 ms 21080 KB Output is correct
21 Correct 4 ms 20828 KB Output is correct
22 Correct 4 ms 20828 KB Output is correct
23 Correct 4 ms 20828 KB Output is correct
24 Correct 4 ms 20992 KB Output is correct
25 Correct 4 ms 20828 KB Output is correct
26 Correct 4 ms 20828 KB Output is correct
27 Correct 4 ms 21000 KB Output is correct
28 Correct 4 ms 20824 KB Output is correct
29 Correct 4 ms 20828 KB Output is correct
30 Correct 219 ms 39596 KB Output is correct
31 Correct 1030 ms 36768 KB Output is correct
32 Correct 240 ms 48720 KB Output is correct
33 Correct 469 ms 38228 KB Output is correct
34 Execution timed out 4026 ms 36944 KB Time limit exceeded
35 Halted 0 ms 0 KB -