oj.uz

Submission #814717

# Submission time Handle Problem Language Result Execution time Memory
814717 2023-08-08T09:16:40 Z konstantys Sprinkler (JOI22_sprinkler) C++14
38 / 100
 2108 ms 223936 KB 
#include<iostream>
#include<cstdlib>
#include<vector>
#include<cassert>
#define ll long long
using namespace std;
int n,q,a,b,c,ojc[200005],d,ojc2[81];
ll L,tab[200005],x;
ll t[200005][42];
ll f[200005][81];
ll p[200005];
vector<int> v[200005];
vector<int> v2[42];
void DFS(int x,int f){
    ojc[x]=f;
    for(auto i:v[x]) if(i!=f) DFS(i,x);
}
void dod2(int x,int p,int k,ll z){
    assert(k==(p+1));
    t[x][p]*=z,t[x][p]%=L;
}
void dod(int x,int k,ll z){
    //od 0 do k
    p[x]*=z,p[x]%=L;
    for(auto u:v2[k])
        f[x][u]*=z,f[x][u]%=L;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin>>n>>L;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        for(int u=0;u<=41;u++) t[i][u]=1;
        for(int u=0;u<80;u++) f[i][u]=1;
        p[i]=1;
        cin>>tab[i];
    }
    for(int u=1;u<=63;u++) ojc2[u]=u>>1;
    ojc2[64]=0;
    for(int u=65;u<=79;u++) ojc2[u]=((u-63)>>1)+63; //fenwick liczy odleglosci od 1
    for(int u=1;u<=32;u++){
        int p=1,k=32,m=1;
        while(true){
            if(k==u){
                v2[u].push_back(m);
                break;
            }
            if(p>u) break;
            if(u>((p+k)>>1)){
                v2[u].push_back(m*2);
                m=m*2+1;
                p=((p+k)>>1)+1;
            }else{
                m=m*2;
                k=((p+k)>>1);
            }

        }
    }
    DFS(1,-1);
    //return 0;
    //cerr<<v2[0].size()<<" rozmiar\n";
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>a;
        if(a==2){
            cin>>b;
            d=0,c=b;
            ll wyn=tab[b];
            //cerr<<wyn<<"\n";
            wyn*=p[c];
            wyn%=L;
            while(true){
                wyn*=t[c][d];
                wyn%=L;
                if(d!=0){
                    wyn*=t[c][d-1];
                    wyn%=L;
                    a=d+31;
                    wyn*=f[c][a];
                    wyn%=L;
                    //cerr<<"f["<<c<<"]["<<a<<"]="<<f[c][a]<<"\n";
                    while(a!=0){
                        a=ojc2[a];
                        //cerr<<"f["<<c<<"]["<<a<<"]="<<f[c][a]<<"\n";
                        wyn*=f[c][a];
                        wyn%=L;
                    }
                }
                c=ojc[c];
                if(c==-1) break;
                d++;
                if(d>32) break;
            }
            cout<<wyn<<"\n";
        }else{
            cin>>b>>c>>x;
            d=0;
            while(true){
                if(b==-1 || d>c) break;
                if(b!=1 && c!=d){
                    //cerr<<b<<" "<<c-d-1<<"\n";
                    dod2(b,c-d-1,c-d,x);
                }else{
                    //cerr<<b<<" "<<c<<"-"<<d<<" "<<" drzewo\n";
                    dod(b,c-d,x);
                }
                b=ojc[b];
                d++;
            }
        }
    }

    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 5 ms 6060 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 1855 ms 219604 KB Output is correct
3 Correct 579 ms 220088 KB Output is correct
4 Correct 1330 ms 222580 KB Output is correct
5 Correct 1336 ms 219824 KB Output is correct
6 Correct 770 ms 219432 KB Output is correct
7 Correct 738 ms 220056 KB Output is correct
8 Correct 503 ms 220612 KB Output is correct
9 Correct 1962 ms 223732 KB Output is correct
10 Correct 550 ms 223844 KB Output is correct
11 Correct 1786 ms 219528 KB Output is correct
12 Correct 473 ms 220052 KB Output is correct
13 Correct 301 ms 220368 KB Output is correct
14 Correct 291 ms 220920 KB Output is correct
15 Correct 294 ms 220152 KB Output is correct
16 Correct 343 ms 220664 KB Output is correct
17 Correct 318 ms 221180 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 5 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 5 ms 5076 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 1855 ms 219604 KB Output is correct
3 Correct 579 ms 220088 KB Output is correct
4 Correct 1330 ms 222580 KB Output is correct
5 Correct 1336 ms 219824 KB Output is correct
6 Correct 770 ms 219432 KB Output is correct
7 Correct 738 ms 220056 KB Output is correct
8 Correct 503 ms 220612 KB Output is correct
9 Correct 1962 ms 223732 KB Output is correct
10 Correct 550 ms 223844 KB Output is correct
11 Correct 1786 ms 219528 KB Output is correct
12 Correct 473 ms 220052 KB Output is correct
13 Correct 301 ms 220368 KB Output is correct
14 Correct 291 ms 220920 KB Output is correct
15 Correct 294 ms 220152 KB Output is correct
16 Correct 343 ms 220664 KB Output is correct
17 Correct 318 ms 221180 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 5 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 5 ms 5076 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 1690 ms 219644 KB Output is correct
25 Correct 515 ms 220088 KB Output is correct
26 Correct 1337 ms 223936 KB Output is correct
27 Correct 1185 ms 219816 KB Output is correct
28 Correct 741 ms 219988 KB Output is correct
29 Correct 706 ms 219616 KB Output is correct
30 Correct 475 ms 220636 KB Output is correct
31 Correct 1935 ms 222532 KB Output is correct
32 Correct 535 ms 223904 KB Output is correct
33 Correct 1640 ms 219524 KB Output is correct
34 Correct 508 ms 220108 KB Output is correct
35 Correct 4 ms 4948 KB Output is correct
36 Correct 3 ms 5040 KB Output is correct
37 Correct 3 ms 5076 KB Output is correct
38 Correct 3 ms 5028 KB Output is correct
39 Correct 3 ms 5032 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 4 ms 4948 KB Output is correct
43 Correct 3 ms 5032 KB Output is correct
44 Correct 4 ms 4948 KB Output is correct
45 Correct 3 ms 4948 KB Output is correct
46 Correct 3 ms 5076 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 3 ms 4956 KB Output is correct
49 Correct 3 ms 5076 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5024 KB Output is correct
2 Incorrect 2106 ms 220896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2108 ms 222092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 5 ms 6060 KB Output isn't correct
5 Halted 0 ms 0 KB -