Submission #1013427

#TimeUsernameProblemLanguageResultExecution timeMemory
10134278pete8Sprinkler (JOI22_sprinkler)C++17
0 / 100
224 ms85168 KiB
#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]; vector<qry>event,event2; struct fen{ int fwk[mxn+10]; void init(int n){for(int i=0;i<=n;i++)fwk[i]=1;} void update(int pos,int val,int n){for(int i=pos;i<=n;i+=(i&-i))fwk[i]=(fwk[i]*val)%k;} int qry(int pos){ if(pos==0)return 1; int ans=1; for(int i=pos;i>0;i-=(i&-i))ans=(ans*fwk[i])%k; return ans; } }t; 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 tin[mxn+10],tout[mxn+10],T=0,in[mxn+10],where[mxn+10],ans[mxn+10]; int inv(int x){ int ex=k-2,ans=1; while(ex){ if(ex&1)ans=(ans*x)%k; x=(x*x)%k; ex>>=1; } return ans; } void dfs(int cur,int p,int deg){ tin[cur]=++T; in[cur]=deg; for(auto i:have[cur]){ event.pb(i); id[i.time]=0; if(i.type==1){ if(i.D-dist[cur]>=0)event2.pb(i); else id[i.time]--; } if(id[i.time]!=-1)bro[deg].pb(i); } for(auto i:adj[cur])if(i!=p&&!del[i]){ dist[i]=dist[cur]+1; dfs(i,cur,deg); } tout[cur]=T; } 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); dist[node]=0; for(auto i:have[node]){ event.pb(i); id[i.time]=0; if(i.type==1){ if(i.D-dist[node]>=0)event2.pb(i); else id[i.time]--; } } T=0; //cout<<cur<<" "<<node<<'\n'; 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(rall(event2)); for(int i=0;i<event2.size();i++)id[event2[i].time]=i+1; t.init(event2.size()); // for(auto i:event2)cout<<i.time<<" "<<i.D<<" "<<i.w<<' '<<dist[i.node]<<' '<<i.node<<"LLL\n"; auto get=[&](int x){ int l=0,r=event2.size()-1,pos=minf; while(l<=r){ int mid=l+(r-l)/2; if(event2[mid].D-dist[event2[mid].node]>=x)l=mid+1,pos=max(pos,mid); else r=mid-1; } if(pos==minf)return 0LL; return pos+1; }; sort(all(event),cmp); for(auto i:event){ if(i.type==1&&id[i.time]!=-1){ t.update(id[i.time],i.w,event2.size()); } else if(i.type==2){ where[i.time]=get(dist[i.node]); //cout<<where[i.time]<<" "<<t.qry(where[i.time])<<" "<<i.node<<" "<<dist[i.node]<<"GG\n"; //cout<<t.qry(where[i.time])<<"PPP\n"; ans[i.time]=(ans[i.time]*t.qry(where[i.time]))%k; } } t.init(event2.size()); for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]]){ sort(all(bro[i]),cmp); for(auto j:bro[i]){ if(j.type==1&&id[j.time]!=-1)t.update(id[j.time],j.w,event2.size()); else if(j.type==2)ans[j.time]=(ans[j.time]*inv(t.qry(where[j.time])))%k; } } event2.clear(); event.clear(); del[node]=1; for(int i=0;i<adj[node].size();i++)bro[i].clear(); for(auto i:adj[node])if(!del[i])solve(i); } int32_t main(){ fastio cin>>n>>k; for(int i=1;i<=n;i++)dist[i]=-1; 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; 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"; //solve(1); } /* 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:53:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 |     void init(int n){for(int i=0;i<=n;i++)fwk[i]=1;}
      |                    ^
sprinkler.cpp:54:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |     void update(int pos,int val,int n){for(int i=pos;i<=n;i+=(i&-i))fwk[i]=(fwk[i]*val)%k;}
      |                                      ^
sprinkler.cpp:55:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 |     int qry(int pos){
      |                    ^
sprinkler.cpp:63:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   63 | void getsz(int cur,int p){
      |                         ^
sprinkler.cpp:68:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | int getcen(int cur,int p,int need){
      |                                  ^
sprinkler.cpp:73:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int inv(int x){
      |              ^
sprinkler.cpp:82:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   82 | void dfs(int cur,int p,int deg){
      |                               ^
sprinkler.cpp:100:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  100 | bool cmp(qry a,qry b){return a.time<b.time;}
      |                     ^
sprinkler.cpp:101:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  101 | void solve(int cur){
      |                   ^
sprinkler.cpp: In function 'void solve(long long int)':
sprinkler.cpp:115: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]
  115 |     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:117:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<event2.size();i++)id[event2[i].time]=i+1;
      |                 ~^~~~~~~~~~~~~~
sprinkler.cpp:120:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  120 |     auto get=[&](int x){
      |                       ^
sprinkler.cpp:143: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]
  143 |     for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]]){
      |                 ~^~~~~~~~~~~~~~~~~
sprinkler.cpp:153: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]
  153 |     for(int i=0;i<adj[node].size();i++)bro[i].clear();
      |                 ~^~~~~~~~~~~~~~~~~
sprinkler.cpp: At global scope:
sprinkler.cpp:156:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  156 | 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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...