Submission #999486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999486	2024-06-15T15:21:09 Z	Saul0906	Sprinkler (JOI22_sprinkler)	C++14	0 / 100	4000 ms	439112 KB

sprinkler

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
#define pll pair<ll, ll>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define repa(a,b) for(auto a:b)
#define endl "\n"
 
using namespace std;
 
const int lim=2e5+5;
vector<int> adj[lim];
int sz[lim], h[lim][20], pos[lim], sum[20], lvl[lim], mx[lim];
pll par[lim];
ll L, H[lim];
bool vis[lim], vis2[lim][20];
 
struct segtree{
	segtree *left, *right;
	int l, r, mid;
	ll v=1;
	segtree(int x=0, int y=lim): l(x), r(y){
		if(l==r) return;
		mid=((l+r)>>1);
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
	}
	void update(int x, int y, ll z){
		if(y<l || r<x) return;
		if(x<=l && r<=y){
			v*=z;
			v%=L;
			return;
		}
		left->update(x,y,z);
		right->update(x,y,z);
	}
	ll query(int x){
		if(x<l || r<x) return 1;
		if(x<=l && r<=x) return v;
		return (((left->query(x)*right->query(x))%L)*v)%L;
	}
} ST[20];
 
void sztree(int u, int p=0){
	sz[u]=1;
	repa(v,adj[u]){
		if(v==p || vis[v]) continue;
		sztree(v,u);
		sz[u]+=sz[v];
	}
}
 
void dis(int u, int l){
	int x=0, d=0;
	queue<int> q;
	q.push(u);
	q.push(0);
	h[u][l]=0;
	vis2[u][l]=true;
	while(q.size()){
		x=q.front();
		q.pop();
		d=q.front();
		q.pop();
		repa(y,adj[x]){
			if(!vis2[y][l] && !vis[y]){
				h[y][lvl[u]]=d+1;
				q.push(y);
				q.push(d+1);
				vis2[y][l]=true;
			}
		}
	}
	pos[u]=sum[l];
	sum[l]+=d+1;
	mx[u]=d;
}
 
pll find_centroid(int u, int p, int r){
	repa(v,adj[u]){
		if(v==p || vis[v]) continue;
		if(sz[v]>sz[r]/2){
			pll x=find_centroid(v,u,r);
			return {x.fi,x.se+1};
		}
	}
	return {u,0};
}
 
void centroid(int u, int p=0, int l=0){
	sztree(u);
	pll x=find_centroid(u,p,u);
	u=x.fi;
	lvl[u]=l;
	par[u]={p,x.se+1};
	dis(u,l);
	vis[u]=true;
	repa(v,adj[u]) if(!vis[v]) centroid(v,u,l+1);
}
 
void update(int u, int d, ll w){
	pll x=par[u];
	while(x.fi){
		if(h[u][lvl[x.fi]]<=d){
			ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+min(d-h[u][lvl[x.fi]],mx[x.fi]),w);
			//cout<<d<<" "<<h[u][lvl[x.fi]]<<" "<<x.fi<<" "<<u<<endl;
		}
		x={par[x.fi].fi,par[x.fi].se+x.se};
	}
	ST[lvl[u]].update(pos[u],pos[u]+min(d,mx[u]),w);
	//cout<<d<<" "<<u<<endl;
}
 
ll query(int u){
	pll x={u,0};
	ll ans=H[u];
	while(x.fi){
		//cout<<u<<" "<<h[u][lvl[x.fi]]<<" "<<ans<<endl;
		ans*=ST[lvl[x.fi]].query(pos[x.fi]+h[u][lvl[x.fi]]);
		ans%=L;
		x=par[x.fi];
	}
	return ans;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, m, u, v;
	cin>>n>>L;
	rep(i,1,n){
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	rep(i,0,n) cin>>H[i+1];
	centroid(u);
	int q;
	cin>>q;
	while(q--){
		ll t, x, d, w;
		cin>>t;
		if(t&1){
			cin>>x>>d>>w;
			update(x,d,w);
		}else{
			cin>>x;
			cout<<query(x)<<endl;
		}
	}
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:134:8: warning: unused variable 'm' [-Wunused-variable]
  134 |  ll n, m, u, v;
      |        ^

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	234 ms	391832 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	227 ms	391672 KB	Output is correct
2	Correct	2547 ms	426588 KB	Output is correct
3	Correct	1266 ms	427088 KB	Output is correct
4	Correct	3615 ms	439112 KB	Output is correct
5	Correct	1875 ms	426808 KB	Output is correct
6	Correct	1408 ms	426424 KB	Output is correct
7	Correct	1180 ms	427120 KB	Output is correct
8	Correct	627 ms	427740 KB	Output is correct
9	Execution timed out	4075 ms	434296 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	227 ms	391672 KB	Output is correct
2	Correct	2547 ms	426588 KB	Output is correct
3	Correct	1266 ms	427088 KB	Output is correct
4	Correct	3615 ms	439112 KB	Output is correct
5	Correct	1875 ms	426808 KB	Output is correct
6	Correct	1408 ms	426424 KB	Output is correct
7	Correct	1180 ms	427120 KB	Output is correct
8	Correct	627 ms	427740 KB	Output is correct
9	Execution timed out	4075 ms	434296 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-