Submission #1013541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013541		8pete8	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2957 ms	202948 KiB

sprinkler

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
vector<int>adj[mxn+10];
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
int h[mxn+10],dist[mxn+10],sz[mxn+10],del[mxn+10],id[mxn+10];
struct qry{
    int time,node,D,w,type;
    bool operator<(qry a)const{return D-dist[node]<=a.D-dist[a.node];};
};
vector<qry>have[mxn+10],event;
struct seg{
    int v[2*mxn+10];
    void init(int n){for(int i=0;i<=2*n;i++)v[i]=1;}
    void update(int pos,int val,int n){
        pos+=n;
        v[pos]=(v[pos]*val)%k;
        for(int i=pos;i>0;i>>=1)v[i>>1]=(v[i]*v[i^1])%k;
    }
    int qry(int l,int r,int n){
        int ans=1;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=(ans*v[l++])%k;
            if(!(r&1))ans=(ans*v[r--])%k;
        }
        return ans;
    }
}t2[45];
vector<qry>bro[mxn+10];
void getsz(int cur,int p){
    sz[cur]=1,dist[cur]=0;
    for(auto i:adj[cur])if(i!=p&&!del[i])getsz(i,cur),sz[cur]+=sz[i];
}
int getcen(int cur,int p,int need){
    for(auto i:adj[cur])if(i!=p&&sz[i]>=need&&!del[i])return getcen(i,cur,need);
    return cur;
}
int in[mxn+10],where[mxn+10],ans[mxn+10];
void dfs(int cur,int p,int deg){
    in[cur]=deg;
    for(auto i:have[cur]){
        if(i.type==1){
            if(i.D-dist[cur]>=0)event.pb(i);
        }
        else event.pb(i);
    }
    for(auto i:adj[cur])if(i!=p&&!del[i]){
        dist[i]=dist[cur]+1;
        dfs(i,cur,deg);
    }
}
bool cmp(qry a,qry b){return a.time<b.time;}
void solve(int cur){
    getsz(cur,-1);
    int node=getcen(cur,-1,sz[cur]/2);
    for(auto i:have[node]){
        if(i.type==1){
            if(i.D-dist[node]>=0)event.pb(i);
        }
        else event.pb(i);
    }
    for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]])dist[adj[node][i]]=1,dfs(adj[node][i],node,i);
    sort(all(event),cmp);
    for(int i=0;i<=40;i++)t2[i].init(adj[node].size()+1);
    vector<int>ex(41,1);
    for(auto i:event){
        if(i.type==1&&id[i.time]!=-1){
            if(i.node==node)ex[i.D-dist[i.node]]=(ex[i.D-dist[i.node]]*i.w)%k;
            else t2[(i.D-dist[i.node])].update(in[i.node],i.w,adj[node].size());
        }
        else if(i.type==2){
            for(int K=dist[i.node];K<=40;K++){
                ans[i.time]=(ans[i.time]*ex[K])%k;
                if(i.node==node)ans[i.time]=(ans[i.time]*t2[K].qry(0,adj[node].size()-1,adj[node].size()))%k;
                else{
                    if(in[i.node])ans[i.time]=(ans[i.time]*(t2[K].qry(0,in[i.node]-1,adj[node].size())))%k;
                    if(in[i.node]+1<adj[node].size())ans[i.time]=(ans[i.time]*(t2[K].qry(in[i.node]+1,adj[node].size()-1,adj[node].size())))%k;
                }
            }

        }

    }
    event.clear();
    del[node]=1;
    for(auto i:adj[node])if(!del[i])solve(i);
}
int32_t main(){
    fastio
    //d is less than 40 wtf '0'
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i=1;i<=n;i++)cin>>h[i];
    int q;cin>>q;
    vector<int>what;
    for(int i=0;i<q;i++){
        int a;cin>>a;
        qry x;
        x.type=a;
        x.time=i;
        if(a==1){
            cin>>x.node>>x.D>>x.w;
            x.w%=k;
            have[x.node].pb(x);
        }
        else{
            cin>>x.node;
            have[x.node].pb(x);
            what.pb(i);
            ans[i]=h[x.node];
        }
    }
    solve(1);
    for(auto i:what){
        cout<<ans[i]<<"\n";
        if(ans[i]<0)assert(0);
    }
}
/*
4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

*/

Compilation message (stderr)

sprinkler.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
sprinkler.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void setIO(string name){
      |                       ^
sprinkler.cpp:47:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 |     bool operator<(qry a)const{return D-dist[node]<=a.D-dist[a.node];};
      |                          ^~~~~
sprinkler.cpp:52:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 |     void init(int n){for(int i=0;i<=2*n;i++)v[i]=1;}
      |                    ^
sprinkler.cpp:53:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |     void update(int pos,int val,int n){
      |                                      ^
sprinkler.cpp:58:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   58 |     int qry(int l,int r,int n){
      |                              ^
sprinkler.cpp:68:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | void getsz(int cur,int p){
      |                         ^
sprinkler.cpp:72:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   72 | int getcen(int cur,int p,int need){
      |                                  ^
sprinkler.cpp:77:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   77 | void dfs(int cur,int p,int deg){
      |                               ^
sprinkler.cpp:90:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   90 | bool cmp(qry a,qry b){return a.time<b.time;}
      |                     ^
sprinkler.cpp:91:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   91 | void solve(int cur){
      |                   ^
sprinkler.cpp: In function 'void solve(long long int)':
sprinkler.cpp:100:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]])dist[adj[node][i]]=1,dfs(adj[node][i],node,i);
      |                 ~^~~~~~~~~~~~~~~~~
sprinkler.cpp:115:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                     if(in[i.node]+1<adj[node].size())ans[i.time]=(ans[i.time]*(t2[K].qry(in[i.node]+1,adj[node].size()-1,adj[node].size())))%k;
      |                        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp: At global scope:
sprinkler.cpp:126:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  126 | int32_t main(){
      |              ^
sprinkler.cpp: In function 'void setIO(std::string)':
sprinkler.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17