oj.uz

Submission #875766

# Submission time Handle Problem Language Result Execution time Memory
875766 2023-11-20T12:52:35 Z danikoynov Sprinkler (JOI22_sprinkler) C++14
0 / 100
 4000 ms 57560 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;
    }
}


void offline_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == 1)
            task[ask[i].ver].push_back(ask[i]);
    }

    for (int i = 1; i <= n; i ++)
        sort(task[i].begin(), task[i].end(), cmp);
}

int par[maxn];
void dfs(int v)
{
    for (int u : adj[v])
    {
        if (u == par[v])
            continue;
        par[u] = v;
        dfs(u);
    }
}

const int maxd = 40;
void make_query(int v, int t)
{
    int cnt = 1, u = par[v];
    ll ans = h[v];
    while(u != 0 && cnt <= maxd)
    {
        for (query cur : task[u])
        {
            ///cout << "check " << v << " : " << u << " : " << cur.t << " : " << t << " " << cur.d << endl;
            if (cur.t <= t && cur.d >= cnt)
                ans = (ans * cur.w) % l;///, cout << "change " << ans << endl;
        }
        cnt ++;
        u = par[u];
    }
    cout << ans << endl;
}
void simulate()
{
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == 2)
            make_query(ask[i].ver, i);
        else
        {
            int ver = ask[i].ver, cnt = 0;
            while(cnt <= ask[i].d && ver != 0)
            {
                ///cout << ver << " update " << ask[i].w << endl;
                h[ver] = (h[ver] * ask[i].w) % l;
                ver = par[ver];
                cnt ++;
            }

        }
    }

}
void solve()
{
    input();
    offline_queries();
    dfs(1);
    simulate();
}

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12772 KB Output is correct
4 Incorrect 3 ms 12636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12772 KB Output is correct
2 Correct 386 ms 32636 KB Output is correct
3 Correct 274 ms 52220 KB Output is correct
4 Correct 420 ms 50000 KB Output is correct
5 Correct 316 ms 46420 KB Output is correct
6 Correct 269 ms 45996 KB Output is correct
7 Correct 222 ms 46676 KB Output is correct
8 Correct 202 ms 47044 KB Output is correct
9 Correct 369 ms 46736 KB Output is correct
10 Correct 301 ms 57560 KB Output is correct
11 Correct 358 ms 40840 KB Output is correct
12 Correct 267 ms 52308 KB Output is correct
13 Execution timed out 4053 ms 54968 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12772 KB Output is correct
2 Correct 386 ms 32636 KB Output is correct
3 Correct 274 ms 52220 KB Output is correct
4 Correct 420 ms 50000 KB Output is correct
5 Correct 316 ms 46420 KB Output is correct
6 Correct 269 ms 45996 KB Output is correct
7 Correct 222 ms 46676 KB Output is correct
8 Correct 202 ms 47044 KB Output is correct
9 Correct 369 ms 46736 KB Output is correct
10 Correct 301 ms 57560 KB Output is correct
11 Correct 358 ms 40840 KB Output is correct
12 Correct 267 ms 52308 KB Output is correct
13 Execution timed out 4053 ms 54968 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Incorrect 396 ms 43836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 393 ms 44552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12772 KB Output is correct
4 Incorrect 3 ms 12636 KB Output isn't correct
5 Halted 0 ms 0 KB -