oj.uz

Submission #637974

# Submission time Handle Problem Language Result Execution time Memory
637974 2022-09-03T18:52:19 Z victor_gao Sprinkler (JOI22_sprinkler) C++17
38 / 100
 3724 ms 1048576 KB 
#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 200002
#define MAXT 25
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,L,loc[N],sz[N],fa[N],h[N];
vector<int>g[N];
struct BIT_2D{
    vector<int>bit[44];
    int n=0,m=MAXT+2;
    inline void init(int _n){
        n=_n;
        for (int i=0;i<=m;i++)
            bit[i].resize(n+1,1);
    }
    inline void modify(int x,int y,int c){
        x=m-x;
       // cout<<"modify : "<<x<<' '<<y<<" "<<c<<'\n';
        while (x<=m){
            int ty=y;
            while (ty<=n){
                bit[x][ty]=(long long)(bit[x][ty])*(long long)c%(long long)L;
                ty+=ty&(-ty);
            }
            x+=x&(-x);
        }
    }
    inline long long query(int x,int y){
        long long ans=1;
        x=m-x;
      //  cout<<"query : "<<x<<' '<<y<<'\n';
        while (x>0){
            int ty=y;
            while (ty>0){
                ans=ans*(long long)(bit[x][ty])%L;
                ty-=ty&(-ty);
            }
            x-=x&(-x);
        }
        return ans;
    }
}cntl[N],cntr[N];
inline void dfs(int p,int lp){
    fa[p]=lp;
    for (auto i:g[p]){
        if (i!=lp){
            dfs(i,p);
            sz[p]++;
            loc[i]=sz[p];
        }
    }
}
signed main(){
    fast
    cin>>n>>L;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1;i<=n;i++)
        cin>>h[i];
    dfs(1,0);
    loc[1]=1; sz[0]=1;
    for (int i=0;i<=n;i++){
        sz[i]++;
        cntl[i].init(sz[i]);
        cntr[i].init(sz[i]);
    }
    int q; cin>>q;
    while (q--){
        int type,x,d,w; cin>>type;
        if (type==1){
            cin>>x>>d>>w;
            cntl[x].modify(d,1,w);
            for (int i=0;i<d;i++){
                if (x==0) break;
                int pos=loc[x];
              //  cout<<x<<" "<<fa[x]<<' '<<pos<<" "<<d-i+1<<'\n';
                cntl[fa[x]].modify(d-i-1,pos+1,w);
                cntr[fa[x]].modify(d-i-1,sz[fa[x]]-pos+1,w);
               // cout<<"dis : "<<d-i+1<<" OK\n";
                x=fa[x];
            }
        }
        else {
            cin>>x;
            long long ans=h[x];
            long long tans1=cntl[x].query(0,sz[x]),tans2;
            ans=(ans*tans1)%L;
         //   cout<<" -> "<<tans1<<'\n';
            for (int i=1;i<MAXT;i++){
                if (x==0) break;
                int pos=loc[x];
                tans1=cntl[fa[x]].query(i,pos);
                tans2=cntr[fa[x]].query(i,sz[fa[x]]-pos);
              //  cout<<" -> "<<tans1<<' '<<tans2<<'\n';
                ans=(ans*tans1%L*tans2)%L;
                x=fa[x];
            }
            cout<<ans<<'\n';
        }
    }
}

Compilation message

sprinkler.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
      |                                                                                        ^
sprinkler.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
sprinkler.cpp:22:28: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   22 |     inline void init(int _n){
      |                            ^
sprinkler.cpp:22:28: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:28: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   27 |     inline void modify(int x,int y,int c){
      |                                         ^
sprinkler.cpp:27:41: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:41: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   39 |     inline long long query(int x,int y){
      |                                       ^
sprinkler.cpp:39:39: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:39: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   54 | inline void dfs(int p,int lp){
      |                             ^
sprinkler.cpp:54:29: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:29: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   64 | signed main(){
      |             ^
sprinkler.cpp:64:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:64:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 421416 KB Output is correct
2 Correct 218 ms 421472 KB Output is correct
3 Correct 217 ms 421404 KB Output is correct
4 Runtime error 523 ms 858156 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 421364 KB Output is correct
2 Correct 3519 ms 785692 KB Output is correct
3 Correct 1642 ms 782556 KB Output is correct
4 Correct 2762 ms 787812 KB Output is correct
5 Correct 2685 ms 784304 KB Output is correct
6 Correct 1755 ms 789360 KB Output is correct
7 Correct 1617 ms 795368 KB Output is correct
8 Correct 1344 ms 828184 KB Output is correct
9 Correct 3669 ms 791608 KB Output is correct
10 Correct 1678 ms 788012 KB Output is correct
11 Correct 3447 ms 785880 KB Output is correct
12 Correct 1617 ms 782788 KB Output is correct
13 Correct 1097 ms 822160 KB Output is correct
14 Correct 1144 ms 822532 KB Output is correct
15 Correct 1322 ms 822248 KB Output is correct
16 Correct 1305 ms 821956 KB Output is correct
17 Correct 1322 ms 822480 KB Output is correct
18 Correct 222 ms 421572 KB Output is correct
19 Correct 226 ms 421468 KB Output is correct
20 Correct 222 ms 421488 KB Output is correct
21 Correct 223 ms 421388 KB Output is correct
22 Correct 222 ms 421488 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 421364 KB Output is correct
2 Correct 3519 ms 785692 KB Output is correct
3 Correct 1642 ms 782556 KB Output is correct
4 Correct 2762 ms 787812 KB Output is correct
5 Correct 2685 ms 784304 KB Output is correct
6 Correct 1755 ms 789360 KB Output is correct
7 Correct 1617 ms 795368 KB Output is correct
8 Correct 1344 ms 828184 KB Output is correct
9 Correct 3669 ms 791608 KB Output is correct
10 Correct 1678 ms 788012 KB Output is correct
11 Correct 3447 ms 785880 KB Output is correct
12 Correct 1617 ms 782788 KB Output is correct
13 Correct 1097 ms 822160 KB Output is correct
14 Correct 1144 ms 822532 KB Output is correct
15 Correct 1322 ms 822248 KB Output is correct
16 Correct 1305 ms 821956 KB Output is correct
17 Correct 1322 ms 822480 KB Output is correct
18 Correct 222 ms 421572 KB Output is correct
19 Correct 226 ms 421468 KB Output is correct
20 Correct 222 ms 421488 KB Output is correct
21 Correct 223 ms 421388 KB Output is correct
22 Correct 222 ms 421488 KB Output is correct
23 Correct 219 ms 421480 KB Output is correct
24 Correct 3512 ms 785776 KB Output is correct
25 Correct 1927 ms 782760 KB Output is correct
26 Correct 2760 ms 789732 KB Output is correct
27 Correct 2529 ms 784220 KB Output is correct
28 Correct 1795 ms 789488 KB Output is correct
29 Correct 1688 ms 795244 KB Output is correct
30 Correct 1302 ms 828176 KB Output is correct
31 Correct 3724 ms 789552 KB Output is correct
32 Correct 1905 ms 787884 KB Output is correct
33 Correct 3503 ms 785760 KB Output is correct
34 Correct 1845 ms 782800 KB Output is correct
35 Correct 220 ms 421380 KB Output is correct
36 Correct 220 ms 421448 KB Output is correct
37 Correct 227 ms 421516 KB Output is correct
38 Correct 219 ms 421460 KB Output is correct
39 Correct 220 ms 421600 KB Output is correct
40 Correct 219 ms 421564 KB Output is correct
41 Correct 224 ms 421540 KB Output is correct
42 Correct 219 ms 421488 KB Output is correct
43 Correct 220 ms 421504 KB Output is correct
44 Correct 226 ms 421480 KB Output is correct
45 Correct 222 ms 421452 KB Output is correct
46 Correct 217 ms 421560 KB Output is correct
47 Correct 220 ms 421452 KB Output is correct
48 Correct 218 ms 421476 KB Output is correct
49 Correct 223 ms 421536 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 421488 KB Output is correct
2 Runtime error 1245 ms 1048576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 421356 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 421416 KB Output is correct
2 Correct 218 ms 421472 KB Output is correct
3 Correct 217 ms 421404 KB Output is correct
4 Runtime error 523 ms 858156 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -