oj.uz

Submission #925132

# Submission time Handle Problem Language Result Execution time Memory
925132 2024-02-10T20:04:29 Z alexdd Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 196176 KB 
#include<bits/stdc++.h>
using namespace std;

/*ifstream fin("02-02.txt");
ofstream fout("output.out");
#define cin fin
#define cout fout*/

#define int long long
int n,MOD,phi;

int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}

int inm[200005];
int qry_brut(int poz)
{
    return inm[poz];
}
void upd_brut(int le, int ri, int newv)
{
    for(int i=le;i<=ri;i++)
        inm[i]=(inm[i]*newv)%MOD;
}

int aib[200005];
int qry(int poz)
{
    int aux=1;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux = (aux * aib[i])%MOD;
    return aux;
}
void upd(int poz, int newv)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib[i] = (aib[i] * newv)%MOD;
}

int aib0[200005];
int qry0(int poz)
{
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux+=aib0[i];
    return aux;
}
void upd0(int poz, int newv)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib0[i]+=newv;
}

int h[200005];
vector<int> con[200005];
int parent[200005];
int tole[200005][45];
int tori[200005][45];
int cntd[200005];
int cntd2[200005];
int depth[200005];
int pos[200005];
void dfs(int nod)
{
    cntd[depth[nod]]++;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            depth[adj]=depth[nod]+1;
            parent[adj]=nod;
            dfs(adj);
        }
    }
}
void dfs2(int nod)
{
    cntd2[depth[nod]]++;
    pos[nod] = cntd[depth[nod]-1] + cntd2[depth[nod]];
    //cout<<nod<<" "<<pos[nod]<<" pos\n";
    for(int d=0;d<=42;d++)
    {
        tole[nod][d] = n+5;
        tori[nod][d] = -1;
    }
    tole[nod][0] = tori[nod][0] = pos[nod];
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            dfs2(adj);
            for(int d=1;d<=42;d++)
            {
                tole[nod][d] = min(tole[nod][d], tole[adj][d-1]);
                tori[nod][d] = max(tori[nod][d], tori[adj][d-1]);
            }
        }
    }
}
void faupd(int le, int ri, int newv, int inv)
{
    if(le>ri)
        return;
    if(newv!=0)
    {
        upd(le,newv);
        upd(ri+1,inv);

        upd_brut(le,ri,newv);
    }
    else
    {
        upd0(le,1);
        upd0(ri+1,-1);
    }
}
int calc_phi(int x)
{
    int d=2,prod=x;
    while(d*d<=x)
    {
        if(x%d==0)
        {
            while(x%d==0)
                x/=d;
            prod = prod / d * (d-1);
        }
        if(d==2)
            d--;
        d+=2;
    }
    if(x>1)
        prod = prod / x * (x-1);
    return prod;
}
int getrez(int poz)
{
    if(qry0(poz)>0)
        return 0;
    else
        return qry_brut(poz);
}
int le[200005],ri[200005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>MOD;
    phi = calc_phi(MOD);
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    depth[1]=1;
    dfs(1);
    for(int i=2;i<=n;i++)
        cntd[i]+=cntd[i-1];
    dfs2(1);
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
        aib[i]=1;
        inm[i]=1;
    }
    int cntq,tip,d;
    cin>>cntq;
    for(int pas=1;pas<=cntq;pas++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>a>>d>>b;
            for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++)
            {
                le[i]=n+5;
                ri[i]=-1;
            }
            int cur=a;
            for(int i=0;i<=d;i++)
            {
                if(cur==0)
                    break;
                for(int j=0;j<=d-i;j++)
                {
                    if(depth[cur]+j>n)
                        break;
                    le[depth[cur]+j] = min(le[depth[cur]+j], tole[cur][j]);
                    ri[depth[cur]+j] = max(ri[depth[cur]+j], tori[cur][j]);
                }
                cur = parent[cur];
            }
            int inv=put(b,phi-1);
            for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++)
            {
                faupd(le[i],ri[i],b,inv);
            }
        }
        else
        {
            cin>>a;
            cout<<(h[a]*getrez(pos[a]))%MOD<<"\n";
            //cout<<h[a]<<" "<<qry_brut(pos[a])<<" zzz\n";
        }
    }
    return 0;
}
/**

*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 3 ms 25080 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Correct 6 ms 25088 KB Output is correct
5 Correct 7 ms 24924 KB Output is correct
6 Correct 8 ms 24924 KB Output is correct
7 Correct 8 ms 24920 KB Output is correct
8 Correct 8 ms 25168 KB Output is correct
9 Correct 4 ms 24920 KB Output is correct
10 Correct 4 ms 25092 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 5 ms 24924 KB Output is correct
13 Correct 4 ms 24924 KB Output is correct
14 Correct 4 ms 25064 KB Output is correct
15 Correct 4 ms 24924 KB Output is correct
16 Correct 4 ms 24924 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 25020 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 4 ms 24924 KB Output is correct
24 Correct 4 ms 24924 KB Output is correct
25 Correct 4 ms 24924 KB Output is correct
26 Correct 4 ms 24920 KB Output is correct
27 Correct 4 ms 24924 KB Output is correct
28 Correct 4 ms 24924 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 363 ms 173824 KB Output is correct
3 Correct 573 ms 182664 KB Output is correct
4 Correct 510 ms 191572 KB Output is correct
5 Correct 461 ms 182356 KB Output is correct
6 Correct 428 ms 181844 KB Output is correct
7 Correct 453 ms 182868 KB Output is correct
8 Correct 400 ms 182976 KB Output is correct
9 Correct 403 ms 196176 KB Output is correct
10 Correct 675 ms 195428 KB Output is correct
11 Correct 321 ms 182104 KB Output is correct
12 Correct 664 ms 182532 KB Output is correct
13 Execution timed out 4105 ms 175376 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 363 ms 173824 KB Output is correct
3 Correct 573 ms 182664 KB Output is correct
4 Correct 510 ms 191572 KB Output is correct
5 Correct 461 ms 182356 KB Output is correct
6 Correct 428 ms 181844 KB Output is correct
7 Correct 453 ms 182868 KB Output is correct
8 Correct 400 ms 182976 KB Output is correct
9 Correct 403 ms 196176 KB Output is correct
10 Correct 675 ms 195428 KB Output is correct
11 Correct 321 ms 182104 KB Output is correct
12 Correct 664 ms 182532 KB Output is correct
13 Execution timed out 4105 ms 175376 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 891 ms 185376 KB Output is correct
3 Execution timed out 4088 ms 181352 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 1226 ms 183384 KB Output is correct
3 Execution timed out 4093 ms 184604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 3 ms 25080 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Correct 6 ms 25088 KB Output is correct
5 Correct 7 ms 24924 KB Output is correct
6 Correct 8 ms 24924 KB Output is correct
7 Correct 8 ms 24920 KB Output is correct
8 Correct 8 ms 25168 KB Output is correct
9 Correct 4 ms 24920 KB Output is correct
10 Correct 4 ms 25092 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 5 ms 24924 KB Output is correct
13 Correct 4 ms 24924 KB Output is correct
14 Correct 4 ms 25064 KB Output is correct
15 Correct 4 ms 24924 KB Output is correct
16 Correct 4 ms 24924 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 25020 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 4 ms 24924 KB Output is correct
24 Correct 4 ms 24924 KB Output is correct
25 Correct 4 ms 24924 KB Output is correct
26 Correct 4 ms 24920 KB Output is correct
27 Correct 4 ms 24924 KB Output is correct
28 Correct 4 ms 24924 KB Output is correct
29 Correct 4 ms 24924 KB Output is correct
30 Correct 363 ms 173824 KB Output is correct
31 Correct 573 ms 182664 KB Output is correct
32 Correct 510 ms 191572 KB Output is correct
33 Correct 461 ms 182356 KB Output is correct
34 Correct 428 ms 181844 KB Output is correct
35 Correct 453 ms 182868 KB Output is correct
36 Correct 400 ms 182976 KB Output is correct
37 Correct 403 ms 196176 KB Output is correct
38 Correct 675 ms 195428 KB Output is correct
39 Correct 321 ms 182104 KB Output is correct
40 Correct 664 ms 182532 KB Output is correct
41 Execution timed out 4105 ms 175376 KB Time limit exceeded
42 Halted 0 ms 0 KB -