oj.uz

Submission #978648

# Submission time Handle Problem Language Result Execution time Memory
978648 2024-05-09T12:23:27 Z vjudge1 Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 120144 KB 
#include <bits/stdc++.h>

using namespace std;

int n,L,q;
vector<int> g[200005],f[200005];
int t[200005];
int h[200005],tin[200005],curtin;
int v[200005],pos[200005];
int firstson[200005][45],lastson[200005][45];

void dfs(int nod)
{
    tin[nod] = ++curtin;
    for (auto vecin : g[nod])
    {
        if (vecin != t[nod])
        {
            t[vecin] = nod;
            f[nod].push_back(vecin);
            h[vecin] = 1 + h[nod];
            dfs(vecin);
        }
    }
}

bool cmp(int x,int y)
{
    if (h[x] != h[y])
        return h[x] < h[y];
    return tin[x] < tin[y];
}

int aint[800005];

int vkk[200005];

int bulan = 40;

void update(int nod,int l,int r,int st,int dr,int val)
{
    if (r < st or dr < l)
        return;
    st = max(st,l);
    dr = min(dr,r);
    if (st == l and r == dr)
    {
        aint[nod] = 1ll * aint[nod] * val % L;
        //cout << nod << ' ' << l << ' ' << r << ' ' << aint[nod] << endl;
        return;
    }
    if (dr - st + 1 <= bulan)
    {
        for (int i = st; i <= dr; i++)
            vkk[i] = 1ll * vkk[i] * val % L;
        return;
    }
    int mij = (l + r) / 2;
    update(2 * nod,l,mij,st,dr,val);
    update(2 * nod + 1,mij + 1,r,st,dr,val);
}

int paint[200005];

void build(int nod,int l,int r)
{
    if (l == r)
        paint[l] = nod;
    else
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> L;
    for (int i = 1; i < n; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        v[i] = i;
    sort(v + 1,v + n + 1,cmp);
    for (int i = 1; i <= n; i++)
        pos[v[i]] = i;
    for (int i = 1; i <= 4 * n; i++)
        aint[i] = 1;
    build(1,1,n);
    for (int i = 1; i <= n; i++)
        vkk[i] = 1;
    for (int i = 1; i <= n; i++)
    {
        int xx;
        cin >> xx;
        update(1,1,n,pos[i],pos[i],xx);
    }
    for (int i = 1; i <= n; i++)
    {
        int nod = i;
        for (int j = 0; j <= 40; j++)
        {
            if (firstson[nod][j] == 0 or pos[i] < pos[firstson[nod][j]])
                firstson[nod][j] = i;
            if (lastson[nod][j] == 0 or pos[i] > pos[lastson[nod][j]])
                lastson[nod][j] = i;
            nod = t[nod];
            if (nod == 0)
                break;
        }
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int tip;
        cin >> tip;
        if (tip == 1)
        {
            int x,d,w;
            cin >> x >> d >> w;
            vector<int> ruta;
            int nod = x;
            for (int j = 0; j <= min(d,h[x]); j++)
            {
                ruta.push_back(nod);
                nod = t[nod];
            }
            nod = ruta.back();
            ruta.pop_back();
            int dist = d - (h[x] - h[nod]);
            for (int j = 0; j <= dist; j++)
            {
                if (firstson[nod][j] == 0)
                    break;
                int lu = pos[firstson[nod][j]],ru = pos[lastson[nod][j]];
                update(1,1,n,lu,ru,w);
            }
            while (!ruta.empty())
            {
                nod = ruta.back();
                ruta.pop_back();
                int dist = d - (h[x] - h[nod]);
                for (int j = dist - 1; j <= dist; j++)
                {
                    if (firstson[nod][j] == 0)
                        break;
                    int lu = pos[firstson[nod][j]],ru = pos[lastson[nod][j]];
                    update(1,1,n,lu,ru,w);
                }
            }
        }
        else
        {
            int x;
            cin >> x;
            int vjj = vkk[pos[x]];
            x = paint[pos[x]];
            int rsp = 1ll * aint[1] * vjj % L;
            while (x != 1)
            {
                rsp = 1ll * rsp * aint[x] % L;
                x /= 2;
            }
            //cout << pos[x] << ' ';
            cout << rsp << '\n';
        }
    }
    return 0;
}

/**
Rezolvarea se bazeaza pe faptul ca D mic
Dupa ce fac ordinea dfs, pun nodurile intr-un sir sortate dupa inaltime si, la egalitate, dupa tin
La un update, iau al max(h[i],D)-lea stramos al lui x, fie el y. Updatez, pe inaltimile h[y] + k pentru k de la 0 la D - (h[x] - h[y]), subarborele
Apoi, merg nod dupa nod cu y spre x, la fiecare pas updatez ultimele doua nivele la care ajunge nodul curent y
Un update este de range prod si query de point value, deci pot face cu un aib care tine chestiile modulo L
Complexitate update: D * log, query: log
Pentru a afla care sunt primul si ultimul nod de la o inaltime care sunt in subarborele meu, inaltime <= D + h[nod], pot doar sa precalculez in N*D

Complexitate: O(N * D + N * logN + Q * D * logN)

Exista o micuta problema, aib-ul nu cred ca isi face treaba deoarece L nu e prim, incercam aint si fingers crossed sa nu dea TLE
**/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 5 ms 15196 KB Output is correct
5 Correct 5 ms 15196 KB Output is correct
6 Correct 5 ms 15320 KB Output is correct
7 Correct 5 ms 15196 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 3 ms 14828 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14768 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14776 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14680 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 4 ms 14684 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 574 ms 102624 KB Output is correct
3 Correct 661 ms 99504 KB Output is correct
4 Correct 678 ms 113436 KB Output is correct
5 Correct 619 ms 101092 KB Output is correct
6 Correct 411 ms 100232 KB Output is correct
7 Correct 396 ms 100224 KB Output is correct
8 Correct 304 ms 98676 KB Output is correct
9 Correct 627 ms 120144 KB Output is correct
10 Correct 771 ms 115528 KB Output is correct
11 Correct 564 ms 102796 KB Output is correct
12 Correct 674 ms 99532 KB Output is correct
13 Correct 410 ms 97984 KB Output is correct
14 Correct 469 ms 97596 KB Output is correct
15 Correct 419 ms 97876 KB Output is correct
16 Correct 385 ms 97360 KB Output is correct
17 Correct 457 ms 98640 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 4 ms 14684 KB Output is correct
22 Correct 3 ms 14680 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 574 ms 102624 KB Output is correct
3 Correct 661 ms 99504 KB Output is correct
4 Correct 678 ms 113436 KB Output is correct
5 Correct 619 ms 101092 KB Output is correct
6 Correct 411 ms 100232 KB Output is correct
7 Correct 396 ms 100224 KB Output is correct
8 Correct 304 ms 98676 KB Output is correct
9 Correct 627 ms 120144 KB Output is correct
10 Correct 771 ms 115528 KB Output is correct
11 Correct 564 ms 102796 KB Output is correct
12 Correct 674 ms 99532 KB Output is correct
13 Correct 410 ms 97984 KB Output is correct
14 Correct 469 ms 97596 KB Output is correct
15 Correct 419 ms 97876 KB Output is correct
16 Correct 385 ms 97360 KB Output is correct
17 Correct 457 ms 98640 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 4 ms 14684 KB Output is correct
22 Correct 3 ms 14680 KB Output is correct
23 Correct 3 ms 14684 KB Output is correct
24 Correct 615 ms 102768 KB Output is correct
25 Correct 728 ms 99520 KB Output is correct
26 Correct 701 ms 117724 KB Output is correct
27 Correct 646 ms 101388 KB Output is correct
28 Correct 416 ms 100436 KB Output is correct
29 Correct 451 ms 100308 KB Output is correct
30 Correct 382 ms 98704 KB Output is correct
31 Correct 682 ms 115312 KB Output is correct
32 Correct 866 ms 115976 KB Output is correct
33 Correct 646 ms 102764 KB Output is correct
34 Correct 811 ms 99456 KB Output is correct
35 Correct 4 ms 14680 KB Output is correct
36 Correct 3 ms 14684 KB Output is correct
37 Correct 3 ms 14684 KB Output is correct
38 Correct 3 ms 14780 KB Output is correct
39 Correct 5 ms 14684 KB Output is correct
40 Correct 3 ms 14684 KB Output is correct
41 Correct 4 ms 14680 KB Output is correct
42 Correct 3 ms 14684 KB Output is correct
43 Correct 3 ms 14684 KB Output is correct
44 Correct 4 ms 14684 KB Output is correct
45 Correct 3 ms 14684 KB Output is correct
46 Correct 3 ms 14684 KB Output is correct
47 Correct 4 ms 14880 KB Output is correct
48 Correct 3 ms 14684 KB Output is correct
49 Correct 4 ms 14684 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 1131 ms 117156 KB Output is correct
3 Correct 3652 ms 112568 KB Output is correct
4 Correct 1651 ms 113732 KB Output is correct
5 Correct 1517 ms 99592 KB Output is correct
6 Correct 1643 ms 98868 KB Output is correct
7 Correct 1337 ms 98836 KB Output is correct
8 Correct 324 ms 97368 KB Output is correct
9 Correct 1014 ms 112824 KB Output is correct
10 Correct 3726 ms 115168 KB Output is correct
11 Correct 1064 ms 100004 KB Output is correct
12 Execution timed out 4033 ms 99408 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 1091 ms 114828 KB Output is correct
3 Correct 3778 ms 109664 KB Output is correct
4 Correct 1666 ms 112628 KB Output is correct
5 Correct 1551 ms 101296 KB Output is correct
6 Correct 1525 ms 100524 KB Output is correct
7 Correct 1402 ms 100300 KB Output is correct
8 Correct 361 ms 98700 KB Output is correct
9 Correct 1177 ms 119048 KB Output is correct
10 Correct 3670 ms 116040 KB Output is correct
11 Correct 1044 ms 103048 KB Output is correct
12 Correct 3538 ms 99580 KB Output is correct
13 Execution timed out 4033 ms 97476 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 5 ms 15196 KB Output is correct
5 Correct 5 ms 15196 KB Output is correct
6 Correct 5 ms 15320 KB Output is correct
7 Correct 5 ms 15196 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 3 ms 14828 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14768 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14776 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14680 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 4 ms 14684 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct
29 Correct 3 ms 14684 KB Output is correct
30 Correct 574 ms 102624 KB Output is correct
31 Correct 661 ms 99504 KB Output is correct
32 Correct 678 ms 113436 KB Output is correct
33 Correct 619 ms 101092 KB Output is correct
34 Correct 411 ms 100232 KB Output is correct
35 Correct 396 ms 100224 KB Output is correct
36 Correct 304 ms 98676 KB Output is correct
37 Correct 627 ms 120144 KB Output is correct
38 Correct 771 ms 115528 KB Output is correct
39 Correct 564 ms 102796 KB Output is correct
40 Correct 674 ms 99532 KB Output is correct
41 Correct 410 ms 97984 KB Output is correct
42 Correct 469 ms 97596 KB Output is correct
43 Correct 419 ms 97876 KB Output is correct
44 Correct 385 ms 97360 KB Output is correct
45 Correct 457 ms 98640 KB Output is correct
46 Correct 3 ms 14684 KB Output is correct
47 Correct 3 ms 14684 KB Output is correct
48 Correct 3 ms 14684 KB Output is correct
49 Correct 4 ms 14684 KB Output is correct
50 Correct 3 ms 14680 KB Output is correct
51 Correct 3 ms 14684 KB Output is correct
52 Correct 615 ms 102768 KB Output is correct
53 Correct 728 ms 99520 KB Output is correct
54 Correct 701 ms 117724 KB Output is correct
55 Correct 646 ms 101388 KB Output is correct
56 Correct 416 ms 100436 KB Output is correct
57 Correct 451 ms 100308 KB Output is correct
58 Correct 382 ms 98704 KB Output is correct
59 Correct 682 ms 115312 KB Output is correct
60 Correct 866 ms 115976 KB Output is correct
61 Correct 646 ms 102764 KB Output is correct
62 Correct 811 ms 99456 KB Output is correct
63 Correct 4 ms 14680 KB Output is correct
64 Correct 3 ms 14684 KB Output is correct
65 Correct 3 ms 14684 KB Output is correct
66 Correct 3 ms 14780 KB Output is correct
67 Correct 5 ms 14684 KB Output is correct
68 Correct 3 ms 14684 KB Output is correct
69 Correct 4 ms 14680 KB Output is correct
70 Correct 3 ms 14684 KB Output is correct
71 Correct 3 ms 14684 KB Output is correct
72 Correct 4 ms 14684 KB Output is correct
73 Correct 3 ms 14684 KB Output is correct
74 Correct 3 ms 14684 KB Output is correct
75 Correct 4 ms 14880 KB Output is correct
76 Correct 3 ms 14684 KB Output is correct
77 Correct 4 ms 14684 KB Output is correct
78 Correct 3 ms 14684 KB Output is correct
79 Correct 1131 ms 117156 KB Output is correct
80 Correct 3652 ms 112568 KB Output is correct
81 Correct 1651 ms 113732 KB Output is correct
82 Correct 1517 ms 99592 KB Output is correct
83 Correct 1643 ms 98868 KB Output is correct
84 Correct 1337 ms 98836 KB Output is correct
85 Correct 324 ms 97368 KB Output is correct
86 Correct 1014 ms 112824 KB Output is correct
87 Correct 3726 ms 115168 KB Output is correct
88 Correct 1064 ms 100004 KB Output is correct
89 Execution timed out 4033 ms 99408 KB Time limit exceeded
90 Halted 0 ms 0 KB -