oj.uz

답안 #637965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637965 2022-09-03T18:33:36 Z victor_gao Sprinkler (JOI22_sprinkler) C++17
3 / 100
 924 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 int long long
#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=42;
    void init(int _n){
        n=_n;
        for (int i=0;i<=m;i++)
            bit[i].resize(n+2,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]=bit[x][ty]*c%L;
                ty+=ty&(-ty);
            }
            x+=x&(-x);
        }
    }
    int query(int x,int y){
        int ans=1;
        x=m-x;
      //  cout<<"query : "<<x<<' '<<y<<'\n';
        while (x>0){
            int ty=y;
            while (ty>0){
                ans=ans*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;
            int ans=h[x];
            int tans1=cntl[x].query(0,sz[x]),tans2;
            ans=(ans*tans1)%L;
         //   cout<<" -> "<<tans1<<'\n';
            for (int i=1;i<=40;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:21: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   22 |     void init(int _n){
      |                     ^
sprinkler.cpp:22:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:22:21: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   27 |     void modify(int x,int y,int c){
      |                                  ^
sprinkler.cpp:27:34: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:27:34: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   39 |     int query(int x,int y){
      |                          ^
sprinkler.cpp:39:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:39:26: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   54 | void dfs(int p,int lp){
      |                      ^
sprinkler.cpp:54:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sprinkler.cpp:54:22: 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
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 424620 KB Output is correct
2 Correct 234 ms 424752 KB Output is correct
3 Correct 232 ms 424628 KB Output is correct
4 Correct 230 ms 428628 KB Output is correct
5 Correct 223 ms 428272 KB Output is correct
6 Correct 234 ms 428288 KB Output is correct
7 Correct 232 ms 428104 KB Output is correct
8 Correct 233 ms 428212 KB Output is correct
9 Correct 227 ms 424540 KB Output is correct
10 Correct 225 ms 424624 KB Output is correct
11 Correct 230 ms 424640 KB Output is correct
12 Correct 227 ms 424640 KB Output is correct
13 Correct 221 ms 424664 KB Output is correct
14 Correct 230 ms 424532 KB Output is correct
15 Correct 224 ms 424524 KB Output is correct
16 Correct 215 ms 424552 KB Output is correct
17 Correct 217 ms 424720 KB Output is correct
18 Correct 215 ms 424688 KB Output is correct
19 Correct 229 ms 424488 KB Output is correct
20 Correct 215 ms 424628 KB Output is correct
21 Correct 229 ms 424620 KB Output is correct
22 Correct 223 ms 424552 KB Output is correct
23 Correct 218 ms 424624 KB Output is correct
24 Correct 240 ms 424596 KB Output is correct
25 Correct 226 ms 424524 KB Output is correct
26 Correct 235 ms 424576 KB Output is correct
27 Correct 224 ms 424536 KB Output is correct
28 Correct 216 ms 424604 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 424508 KB Output is correct
2 Runtime error 924 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 424508 KB Output is correct
2 Runtime error 924 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 424564 KB Output is correct
2 Runtime error 913 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 424528 KB Output is correct
2 Runtime error 922 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 424620 KB Output is correct
2 Correct 234 ms 424752 KB Output is correct
3 Correct 232 ms 424628 KB Output is correct
4 Correct 230 ms 428628 KB Output is correct
5 Correct 223 ms 428272 KB Output is correct
6 Correct 234 ms 428288 KB Output is correct
7 Correct 232 ms 428104 KB Output is correct
8 Correct 233 ms 428212 KB Output is correct
9 Correct 227 ms 424540 KB Output is correct
10 Correct 225 ms 424624 KB Output is correct
11 Correct 230 ms 424640 KB Output is correct
12 Correct 227 ms 424640 KB Output is correct
13 Correct 221 ms 424664 KB Output is correct
14 Correct 230 ms 424532 KB Output is correct
15 Correct 224 ms 424524 KB Output is correct
16 Correct 215 ms 424552 KB Output is correct
17 Correct 217 ms 424720 KB Output is correct
18 Correct 215 ms 424688 KB Output is correct
19 Correct 229 ms 424488 KB Output is correct
20 Correct 215 ms 424628 KB Output is correct
21 Correct 229 ms 424620 KB Output is correct
22 Correct 223 ms 424552 KB Output is correct
23 Correct 218 ms 424624 KB Output is correct
24 Correct 240 ms 424596 KB Output is correct
25 Correct 226 ms 424524 KB Output is correct
26 Correct 235 ms 424576 KB Output is correct
27 Correct 224 ms 424536 KB Output is correct
28 Correct 216 ms 424604 KB Output is correct
29 Correct 220 ms 424508 KB Output is correct
30 Runtime error 924 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -