oj.uz

Submission #637972

# Submission time Handle Problem Language Result Execution time Memory
637972 2022-09-03T18:48:44 Z victor_gao Sprinkler (JOI22_sprinkler) C++17
38 / 100
 2480 ms 1048704 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
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=18;
    void init(int _n){
        n=_n;
        for (int i=0;i<=m;i++)
            bit[i].resize(n+1,1);
    }
    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);
        }
    }
    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];
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<15;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:21:21: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   21 |     void init(int _n){
      |                     ^
sprinkler.cpp:21:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:21:21: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   26 |     void modify(int x,int y,int c){
      |                                  ^
sprinkler.cpp:26:34: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:26:34: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   38 |     long long query(int x,int y){
      |                                ^
sprinkler.cpp:38:32: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:38:32: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   53 | void dfs(int p,int lp){
      |                      ^
sprinkler.cpp:53:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:53:22: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   63 | signed main(){
      |             ^
sprinkler.cpp:63:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:63:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 421476 KB Output is correct
2 Correct 218 ms 421392 KB Output is correct
3 Correct 267 ms 421404 KB Output is correct
4 Runtime error 506 ms 856860 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 236 ms 421516 KB Output is correct
2 Correct 2354 ms 674460 KB Output is correct
3 Correct 1371 ms 670860 KB Output is correct
4 Correct 1859 ms 676196 KB Output is correct
5 Correct 1840 ms 672472 KB Output is correct
6 Correct 1561 ms 675764 KB Output is correct
7 Correct 1337 ms 679464 KB Output is correct
8 Correct 1020 ms 701556 KB Output is correct
9 Correct 2383 ms 678824 KB Output is correct
10 Correct 1435 ms 677448 KB Output is correct
11 Correct 2338 ms 675352 KB Output is correct
12 Correct 1422 ms 676188 KB Output is correct
13 Correct 992 ms 703048 KB Output is correct
14 Correct 1002 ms 703304 KB Output is correct
15 Correct 1131 ms 703244 KB Output is correct
16 Correct 1142 ms 702960 KB Output is correct
17 Correct 1392 ms 703452 KB Output is correct
18 Correct 238 ms 421588 KB Output is correct
19 Correct 219 ms 421496 KB Output is correct
20 Correct 261 ms 421464 KB Output is correct
21 Correct 226 ms 421424 KB Output is correct
22 Correct 221 ms 421456 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 421516 KB Output is correct
2 Correct 2354 ms 674460 KB Output is correct
3 Correct 1371 ms 670860 KB Output is correct
4 Correct 1859 ms 676196 KB Output is correct
5 Correct 1840 ms 672472 KB Output is correct
6 Correct 1561 ms 675764 KB Output is correct
7 Correct 1337 ms 679464 KB Output is correct
8 Correct 1020 ms 701556 KB Output is correct
9 Correct 2383 ms 678824 KB Output is correct
10 Correct 1435 ms 677448 KB Output is correct
11 Correct 2338 ms 675352 KB Output is correct
12 Correct 1422 ms 676188 KB Output is correct
13 Correct 992 ms 703048 KB Output is correct
14 Correct 1002 ms 703304 KB Output is correct
15 Correct 1131 ms 703244 KB Output is correct
16 Correct 1142 ms 702960 KB Output is correct
17 Correct 1392 ms 703452 KB Output is correct
18 Correct 238 ms 421588 KB Output is correct
19 Correct 219 ms 421496 KB Output is correct
20 Correct 261 ms 421464 KB Output is correct
21 Correct 226 ms 421424 KB Output is correct
22 Correct 221 ms 421456 KB Output is correct
23 Correct 220 ms 421480 KB Output is correct
24 Correct 2434 ms 679448 KB Output is correct
25 Correct 1613 ms 676124 KB Output is correct
26 Correct 1982 ms 683328 KB Output is correct
27 Correct 1872 ms 677872 KB Output is correct
28 Correct 1550 ms 681332 KB Output is correct
29 Correct 1463 ms 685424 KB Output is correct
30 Correct 1078 ms 707820 KB Output is correct
31 Correct 2480 ms 683232 KB Output is correct
32 Correct 1542 ms 681472 KB Output is correct
33 Correct 2318 ms 679396 KB Output is correct
34 Correct 1547 ms 676300 KB Output is correct
35 Correct 227 ms 421472 KB Output is correct
36 Correct 219 ms 421584 KB Output is correct
37 Correct 218 ms 421488 KB Output is correct
38 Correct 224 ms 421504 KB Output is correct
39 Correct 222 ms 421504 KB Output is correct
40 Correct 216 ms 421444 KB Output is correct
41 Correct 226 ms 421452 KB Output is correct
42 Correct 221 ms 421412 KB Output is correct
43 Correct 219 ms 421448 KB Output is correct
44 Correct 226 ms 421496 KB Output is correct
45 Correct 220 ms 421476 KB Output is correct
46 Correct 217 ms 421508 KB Output is correct
47 Correct 221 ms 421452 KB Output is correct
48 Correct 219 ms 421584 KB Output is correct
49 Correct 221 ms 421452 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 421576 KB Output is correct
2 Runtime error 1051 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 421452 KB Output is correct
2 Runtime error 1008 ms 1048704 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 244 ms 421476 KB Output is correct
2 Correct 218 ms 421392 KB Output is correct
3 Correct 267 ms 421404 KB Output is correct
4 Runtime error 506 ms 856860 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -