Submission #978665

#	Time	Username	Problem	Language	Result	Execution time	Memory
978665		vjudge1	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1824 ms	152264 KiB

sprinkler

#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 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17