oj.uz

Submission #978665

# Submission time Handle Problem Language Result Execution time Memory
978665 2024-05-09T13:03:31 Z vjudge1 Sprinkler (JOI22_sprinkler) C++17
100 / 100
 1824 ms 152264 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

using namespace std;

int n,L,q;
vector<int> g[200005];
int f[200005][45];
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;
            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 = 30;

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++)
        for (int j = 0; j <= 40; j++)
            f[i][j] = 1;
    for (int i = 1; i <= n; i++)
    {
        int xx;
        cin >> xx;
        f[i][0] = 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;
                f[nod][j] = 1ll * f[nod][j] * w % L;
                /*int lu = pos[firstson[nod][j]],ru = pos[lastson[nod][j]];
                if (ru - lu + 1 <= bulan)
                {
                    for (int jj = lu; jj <= ru; jj++)
                        vkk[jj] = 1ll * vkk[jj] * w % L;
                }
                else
                    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;
                    f[nod][j] = 1ll * f[nod][j] * w % L;
                    /*int lu = pos[firstson[nod][j]],ru = pos[lastson[nod][j]];
                    if (ru - lu + 1 <= bulan)
                    {
                        for (int jj = lu; jj <= ru; jj++)
                            vkk[jj] = 1ll * vkk[jj] * w % L;
                    }
                    else
                        update(1,1,n,lu,ru,w);*/
                }
            }
        }
        else
        {
            int x;
            cin >> x;
            //x = pos[x];
            int rsp = 1;
            for (int j = 0; j <= 40; j++)
            {
                if (x == 0)
                    break;
                //cout << x << ' ' << f[x][j] << "  ";
                rsp = 1ll * rsp * f[x][j] % L;
                x = t[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 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10516 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11100 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 2 ms 10332 KB Output is correct
10 Correct 2 ms 10332 KB Output is correct
11 Correct 3 ms 10332 KB Output is correct
12 Correct 3 ms 10328 KB Output is correct
13 Correct 3 ms 10332 KB Output is correct
14 Correct 3 ms 10332 KB Output is correct
15 Correct 2 ms 10332 KB Output is correct
16 Correct 3 ms 10328 KB Output is correct
17 Correct 4 ms 10328 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 2 ms 10328 KB Output is correct
20 Correct 3 ms 10328 KB Output is correct
21 Correct 2 ms 10332 KB Output is correct
22 Correct 2 ms 10332 KB Output is correct
23 Correct 3 ms 10332 KB Output is correct
24 Correct 3 ms 10528 KB Output is correct
25 Correct 3 ms 10332 KB Output is correct
26 Correct 3 ms 10332 KB Output is correct
27 Correct 3 ms 10332 KB Output is correct
28 Correct 2 ms 10332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 732 ms 129300 KB Output is correct
3 Correct 636 ms 126104 KB Output is correct
4 Correct 837 ms 137808 KB Output is correct
5 Correct 677 ms 127568 KB Output is correct
6 Correct 391 ms 127576 KB Output is correct
7 Correct 357 ms 128032 KB Output is correct
8 Correct 279 ms 128368 KB Output is correct
9 Correct 879 ms 144356 KB Output is correct
10 Correct 682 ms 140380 KB Output is correct
11 Correct 732 ms 129584 KB Output is correct
12 Correct 634 ms 126152 KB Output is correct
13 Correct 258 ms 126656 KB Output is correct
14 Correct 276 ms 126704 KB Output is correct
15 Correct 262 ms 126596 KB Output is correct
16 Correct 267 ms 126612 KB Output is correct
17 Correct 301 ms 127548 KB Output is correct
18 Correct 3 ms 10332 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct
20 Correct 2 ms 10332 KB Output is correct
21 Correct 3 ms 10328 KB Output is correct
22 Correct 4 ms 10332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 732 ms 129300 KB Output is correct
3 Correct 636 ms 126104 KB Output is correct
4 Correct 837 ms 137808 KB Output is correct
5 Correct 677 ms 127568 KB Output is correct
6 Correct 391 ms 127576 KB Output is correct
7 Correct 357 ms 128032 KB Output is correct
8 Correct 279 ms 128368 KB Output is correct
9 Correct 879 ms 144356 KB Output is correct
10 Correct 682 ms 140380 KB Output is correct
11 Correct 732 ms 129584 KB Output is correct
12 Correct 634 ms 126152 KB Output is correct
13 Correct 258 ms 126656 KB Output is correct
14 Correct 276 ms 126704 KB Output is correct
15 Correct 262 ms 126596 KB Output is correct
16 Correct 267 ms 126612 KB Output is correct
17 Correct 301 ms 127548 KB Output is correct
18 Correct 3 ms 10332 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct
20 Correct 2 ms 10332 KB Output is correct
21 Correct 3 ms 10328 KB Output is correct
22 Correct 4 ms 10332 KB Output is correct
23 Correct 3 ms 10332 KB Output is correct
24 Correct 775 ms 129164 KB Output is correct
25 Correct 683 ms 126592 KB Output is correct
26 Correct 814 ms 142260 KB Output is correct
27 Correct 683 ms 127612 KB Output is correct
28 Correct 399 ms 127828 KB Output is correct
29 Correct 369 ms 127832 KB Output is correct
30 Correct 279 ms 128464 KB Output is correct
31 Correct 901 ms 139904 KB Output is correct
32 Correct 697 ms 139860 KB Output is correct
33 Correct 745 ms 129168 KB Output is correct
34 Correct 722 ms 126208 KB Output is correct
35 Correct 3 ms 10328 KB Output is correct
36 Correct 2 ms 10332 KB Output is correct
37 Correct 3 ms 10328 KB Output is correct
38 Correct 3 ms 10332 KB Output is correct
39 Correct 2 ms 10332 KB Output is correct
40 Correct 2 ms 10332 KB Output is correct
41 Correct 2 ms 10332 KB Output is correct
42 Correct 2 ms 10332 KB Output is correct
43 Correct 2 ms 10332 KB Output is correct
44 Correct 3 ms 10332 KB Output is correct
45 Correct 3 ms 10332 KB Output is correct
46 Correct 2 ms 10332 KB Output is correct
47 Correct 2 ms 10536 KB Output is correct
48 Correct 3 ms 10332 KB Output is correct
49 Correct 3 ms 10332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 1033 ms 141648 KB Output is correct
3 Correct 1694 ms 137088 KB Output is correct
4 Correct 1134 ms 138000 KB Output is correct
5 Correct 959 ms 126320 KB Output is correct
6 Correct 481 ms 126720 KB Output is correct
7 Correct 428 ms 126440 KB Output is correct
8 Correct 276 ms 126672 KB Output is correct
9 Correct 1028 ms 137256 KB Output is correct
10 Correct 1805 ms 139720 KB Output is correct
11 Correct 819 ms 126480 KB Output is correct
12 Correct 1281 ms 125876 KB Output is correct
13 Correct 794 ms 128548 KB Output is correct
14 Correct 937 ms 136648 KB Output is correct
15 Correct 3 ms 10332 KB Output is correct
16 Correct 3 ms 10332 KB Output is correct
17 Correct 3 ms 10332 KB Output is correct
18 Correct 3 ms 10328 KB Output is correct
19 Correct 3 ms 10328 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 1036 ms 139256 KB Output is correct
3 Correct 1811 ms 134040 KB Output is correct
4 Correct 1068 ms 136736 KB Output is correct
5 Correct 902 ms 127704 KB Output is correct
6 Correct 483 ms 127664 KB Output is correct
7 Correct 478 ms 127684 KB Output is correct
8 Correct 278 ms 128180 KB Output is correct
9 Correct 1020 ms 143236 KB Output is correct
10 Correct 1824 ms 140316 KB Output is correct
11 Correct 835 ms 129204 KB Output is correct
12 Correct 1262 ms 126376 KB Output is correct
13 Correct 814 ms 128632 KB Output is correct
14 Correct 905 ms 137056 KB Output is correct
15 Correct 3 ms 10328 KB Output is correct
16 Correct 3 ms 10328 KB Output is correct
17 Correct 2 ms 10516 KB Output is correct
18 Correct 3 ms 10508 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10516 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11100 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 2 ms 10332 KB Output is correct
10 Correct 2 ms 10332 KB Output is correct
11 Correct 3 ms 10332 KB Output is correct
12 Correct 3 ms 10328 KB Output is correct
13 Correct 3 ms 10332 KB Output is correct
14 Correct 3 ms 10332 KB Output is correct
15 Correct 2 ms 10332 KB Output is correct
16 Correct 3 ms 10328 KB Output is correct
17 Correct 4 ms 10328 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 2 ms 10328 KB Output is correct
20 Correct 3 ms 10328 KB Output is correct
21 Correct 2 ms 10332 KB Output is correct
22 Correct 2 ms 10332 KB Output is correct
23 Correct 3 ms 10332 KB Output is correct
24 Correct 3 ms 10528 KB Output is correct
25 Correct 3 ms 10332 KB Output is correct
26 Correct 3 ms 10332 KB Output is correct
27 Correct 3 ms 10332 KB Output is correct
28 Correct 2 ms 10332 KB Output is correct
29 Correct 2 ms 10328 KB Output is correct
30 Correct 732 ms 129300 KB Output is correct
31 Correct 636 ms 126104 KB Output is correct
32 Correct 837 ms 137808 KB Output is correct
33 Correct 677 ms 127568 KB Output is correct
34 Correct 391 ms 127576 KB Output is correct
35 Correct 357 ms 128032 KB Output is correct
36 Correct 279 ms 128368 KB Output is correct
37 Correct 879 ms 144356 KB Output is correct
38 Correct 682 ms 140380 KB Output is correct
39 Correct 732 ms 129584 KB Output is correct
40 Correct 634 ms 126152 KB Output is correct
41 Correct 258 ms 126656 KB Output is correct
42 Correct 276 ms 126704 KB Output is correct
43 Correct 262 ms 126596 KB Output is correct
44 Correct 267 ms 126612 KB Output is correct
45 Correct 301 ms 127548 KB Output is correct
46 Correct 3 ms 10332 KB Output is correct
47 Correct 3 ms 10332 KB Output is correct
48 Correct 2 ms 10332 KB Output is correct
49 Correct 3 ms 10328 KB Output is correct
50 Correct 4 ms 10332 KB Output is correct
51 Correct 3 ms 10332 KB Output is correct
52 Correct 775 ms 129164 KB Output is correct
53 Correct 683 ms 126592 KB Output is correct
54 Correct 814 ms 142260 KB Output is correct
55 Correct 683 ms 127612 KB Output is correct
56 Correct 399 ms 127828 KB Output is correct
57 Correct 369 ms 127832 KB Output is correct
58 Correct 279 ms 128464 KB Output is correct
59 Correct 901 ms 139904 KB Output is correct
60 Correct 697 ms 139860 KB Output is correct
61 Correct 745 ms 129168 KB Output is correct
62 Correct 722 ms 126208 KB Output is correct
63 Correct 3 ms 10328 KB Output is correct
64 Correct 2 ms 10332 KB Output is correct
65 Correct 3 ms 10328 KB Output is correct
66 Correct 3 ms 10332 KB Output is correct
67 Correct 2 ms 10332 KB Output is correct
68 Correct 2 ms 10332 KB Output is correct
69 Correct 2 ms 10332 KB Output is correct
70 Correct 2 ms 10332 KB Output is correct
71 Correct 2 ms 10332 KB Output is correct
72 Correct 3 ms 10332 KB Output is correct
73 Correct 3 ms 10332 KB Output is correct
74 Correct 2 ms 10332 KB Output is correct
75 Correct 2 ms 10536 KB Output is correct
76 Correct 3 ms 10332 KB Output is correct
77 Correct 3 ms 10332 KB Output is correct
78 Correct 3 ms 10588 KB Output is correct
79 Correct 1033 ms 141648 KB Output is correct
80 Correct 1694 ms 137088 KB Output is correct
81 Correct 1134 ms 138000 KB Output is correct
82 Correct 959 ms 126320 KB Output is correct
83 Correct 481 ms 126720 KB Output is correct
84 Correct 428 ms 126440 KB Output is correct
85 Correct 276 ms 126672 KB Output is correct
86 Correct 1028 ms 137256 KB Output is correct
87 Correct 1805 ms 139720 KB Output is correct
88 Correct 819 ms 126480 KB Output is correct
89 Correct 1281 ms 125876 KB Output is correct
90 Correct 794 ms 128548 KB Output is correct
91 Correct 937 ms 136648 KB Output is correct
92 Correct 3 ms 10332 KB Output is correct
93 Correct 3 ms 10332 KB Output is correct
94 Correct 3 ms 10332 KB Output is correct
95 Correct 3 ms 10328 KB Output is correct
96 Correct 3 ms 10328 KB Output is correct
97 Correct 3 ms 10332 KB Output is correct
98 Correct 1036 ms 139256 KB Output is correct
99 Correct 1811 ms 134040 KB Output is correct
100 Correct 1068 ms 136736 KB Output is correct
101 Correct 902 ms 127704 KB Output is correct
102 Correct 483 ms 127664 KB Output is correct
103 Correct 478 ms 127684 KB Output is correct
104 Correct 278 ms 128180 KB Output is correct
105 Correct 1020 ms 143236 KB Output is correct
106 Correct 1824 ms 140316 KB Output is correct
107 Correct 835 ms 129204 KB Output is correct
108 Correct 1262 ms 126376 KB Output is correct
109 Correct 814 ms 128632 KB Output is correct
110 Correct 905 ms 137056 KB Output is correct
111 Correct 3 ms 10328 KB Output is correct
112 Correct 3 ms 10328 KB Output is correct
113 Correct 2 ms 10516 KB Output is correct
114 Correct 3 ms 10508 KB Output is correct
115 Correct 3 ms 10332 KB Output is correct
116 Correct 788 ms 135420 KB Output is correct
117 Correct 1361 ms 138204 KB Output is correct
118 Correct 1163 ms 152264 KB Output is correct
119 Correct 893 ms 137832 KB Output is correct
120 Correct 480 ms 137292 KB Output is correct
121 Correct 464 ms 138100 KB Output is correct
122 Correct 297 ms 138436 KB Output is correct
123 Correct 1065 ms 149512 KB Output is correct
124 Correct 1748 ms 146920 KB Output is correct
125 Correct 845 ms 136804 KB Output is correct
126 Correct 1297 ms 138296 KB Output is correct
127 Correct 1328 ms 138380 KB Output is correct
128 Correct 840 ms 139088 KB Output is correct
129 Correct 936 ms 139860 KB Output is correct