oj.uz

답안 #925079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925079 2024-02-10T17:35:10 Z alexdd Sprinkler (JOI22_sprinkler) C++17
0 / 100
 28 ms 46324 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
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 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 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] = INF;
        tori[nod][d] = -INF;
    }
    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]);
            }
        }
    }
}
int inm[200005];
int imp[200005];
void faupd(int le, int ri, int newv, int inv)
{
    if(le>ri)
        return;
    inm[le] = inm[le]*newv;
    imp[ri+1] = imp[ri+1]*newv;
    upd(le,newv);
    upd(ri+1,inv);
}
int qry_brut(int poz)
{
    int rez=1;
    for(int i=1;i<=poz;i++)
    {
        rez = rez * inm[i];
        rez = rez / imp[i];
    }
    return rez;
}
int calc_phi(int x)
{
    return x-2;
}
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;
        imp[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++)
                {
                    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]*qry_brut(pos[a]))%MOD<<"\n";
            //cout<<h[a]<<" "<<qry_brut(pos[a])<<" zzz\n";
        }
    }
    return 0;///schimba aibu cu aint in cazurile in care ai updateuri care inmultesc cu 0 -----------------------------------------------------------------------
}
/**

le_d = min(tole[ancestor_i][])

*/

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 22872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 22876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 22876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 46324 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 22872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 22872 KB Output isn't correct
2 Halted 0 ms 0 KB -