Submission #978628

#	Time	Username	Problem	Language	Result	Execution time	Memory
978628		vjudge1	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4067 ms	201028 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

#define int long long

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];

void update(int nod,int l,int r,int st,int dr,int val)
{
    if (r < st or dr < l)
        return;
    if (st <= l and r <= dr)
    {
        aint[nod] = aint[nod] * val % L;
        //cout << nod << ' ' << l << ' ' << r << ' ' << aint[nod] << endl;
        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 query(int nod,int l,int r,int pos)
{
    if (l == r)
    {
        //cout << nod << ' ' << l << ' ' << r << ' ' << aint[nod] << endl;
        return aint[nod];
    }
    int mij = (l + r) / 2;
    if (pos <= mij)
        return aint[nod] * query(2 * nod,l,mij,pos) % L;
    else
        return aint[nod] * query(2 * nod + 1,mij + 1,r,pos) % L;
}

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;
    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 rsp = query(1,1,n,pos[x]);
            //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 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17