oj.uz

Submission #998458

# Submission time Handle Problem Language Result Execution time Memory
998458 2024-06-14T02:28:12 Z efishel Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 417924 KB 
//Sprinkler Saul
#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];

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;
	queue<int> q;
	q.push(u);
	q.push(0);
	h[u][l]=0;
	while(q.size()){
		x=q.front();
		q.pop();
		d=q.front();
		q.pop();
		repa(y,adj[x]){
			if(h[y][lvl[u]]>d+1){
				h[y][lvl[u]]=d+1;
				q.push(y);
				q.push(d+1);
			}
		}
	}
	pos[u]=sum[l]+1;
	sum[l]+=d;
	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){
			H[x.fi]*=w;
			H[x.fi]%=L;
			ST[lvl[u]].update(pos[u],pos[u]+max(pos[u],min(d-h[u][lvl[x.fi]],mx[u])),w);
		}
		x={par[x.fi].fi,par[x.fi].se+x.se};
	}
	ST[lvl[u]].update(pos[u],pos[u]+min(d,mx[u]),w);
}

ll query(int u){
	pll x={u,0};
	ll ans=H[u];
	while(x.fi){
		ans*=ST[lvl[x.fi]].query(pos[x.fi]+h[u][lvl[x.fi]]);
		ans%=L;
		x=par[x.fi];
	}
	return ans;
}

void dfs(int u, int p, int d, ll w){
	if(d<0) return;
	H[u]*=w;
	H[u]%=L;
	repa(v,adj[u]){
		if(v==p) continue;
		dfs(v,u,d-1,w);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, m, u, v;
	cin>>n>>L;
	rep(i,0,lim) rep(j,0,20) h[i][j]=1e9;
	rep(i,1,n){
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	rep(i,0,n) cin>>H[i+1];
	int q;
	cin>>q;
	while(q--){
		ll t, x, d, w;
		cin>>t;
		if(t&1){
			cin>>x>>d>>w;
			dfs(x,0,d,w);
		}else{
			cin>>x;
			cout<<H[x]<<endl;
		}
	}

}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:142:8: warning: unused variable 'm' [-Wunused-variable]
  142 |  ll n, m, u, v;
      |        ^
sprinkler.cpp: In function 'void dis(int, int)':
sprinkler.cpp:79:7: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  mx[u]=d;
      |  ~~~~~^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 396368 KB Output is correct
2 Correct 247 ms 398416 KB Output is correct
3 Correct 245 ms 397392 KB Output is correct
4 Correct 232 ms 397392 KB Output is correct
5 Correct 245 ms 397392 KB Output is correct
6 Correct 247 ms 397396 KB Output is correct
7 Correct 249 ms 397396 KB Output is correct
8 Correct 237 ms 397208 KB Output is correct
9 Correct 260 ms 397328 KB Output is correct
10 Correct 231 ms 397212 KB Output is correct
11 Correct 244 ms 399184 KB Output is correct
12 Correct 235 ms 397144 KB Output is correct
13 Correct 261 ms 399476 KB Output is correct
14 Correct 227 ms 397152 KB Output is correct
15 Correct 253 ms 397136 KB Output is correct
16 Correct 243 ms 397316 KB Output is correct
17 Correct 233 ms 397140 KB Output is correct
18 Correct 230 ms 397140 KB Output is correct
19 Correct 232 ms 397256 KB Output is correct
20 Correct 235 ms 397136 KB Output is correct
21 Correct 228 ms 397200 KB Output is correct
22 Correct 229 ms 397124 KB Output is correct
23 Correct 235 ms 397140 KB Output is correct
24 Correct 236 ms 397136 KB Output is correct
25 Correct 237 ms 397156 KB Output is correct
26 Correct 233 ms 397136 KB Output is correct
27 Correct 246 ms 397396 KB Output is correct
28 Correct 232 ms 397260 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 399184 KB Output is correct
2 Correct 368 ms 416852 KB Output is correct
3 Correct 413 ms 417360 KB Output is correct
4 Correct 391 ms 417364 KB Output is correct
5 Correct 428 ms 417032 KB Output is correct
6 Correct 414 ms 416748 KB Output is correct
7 Correct 444 ms 416852 KB Output is correct
8 Execution timed out 4058 ms 411192 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 399184 KB Output is correct
2 Correct 368 ms 416852 KB Output is correct
3 Correct 413 ms 417360 KB Output is correct
4 Correct 391 ms 417364 KB Output is correct
5 Correct 428 ms 417032 KB Output is correct
6 Correct 414 ms 416748 KB Output is correct
7 Correct 444 ms 416852 KB Output is correct
8 Execution timed out 4058 ms 411192 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 400112 KB Output is correct
2 Correct 530 ms 415316 KB Output is correct
3 Correct 1580 ms 416084 KB Output is correct
4 Correct 753 ms 415572 KB Output is correct
5 Correct 2352 ms 414548 KB Output is correct
6 Execution timed out 4064 ms 411156 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 400212 KB Output is correct
2 Correct 494 ms 417924 KB Output is correct
3 Correct 1739 ms 416500 KB Output is correct
4 Correct 713 ms 416980 KB Output is correct
5 Correct 2443 ms 417252 KB Output is correct
6 Execution timed out 4086 ms 411476 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 396368 KB Output is correct
2 Correct 247 ms 398416 KB Output is correct
3 Correct 245 ms 397392 KB Output is correct
4 Correct 232 ms 397392 KB Output is correct
5 Correct 245 ms 397392 KB Output is correct
6 Correct 247 ms 397396 KB Output is correct
7 Correct 249 ms 397396 KB Output is correct
8 Correct 237 ms 397208 KB Output is correct
9 Correct 260 ms 397328 KB Output is correct
10 Correct 231 ms 397212 KB Output is correct
11 Correct 244 ms 399184 KB Output is correct
12 Correct 235 ms 397144 KB Output is correct
13 Correct 261 ms 399476 KB Output is correct
14 Correct 227 ms 397152 KB Output is correct
15 Correct 253 ms 397136 KB Output is correct
16 Correct 243 ms 397316 KB Output is correct
17 Correct 233 ms 397140 KB Output is correct
18 Correct 230 ms 397140 KB Output is correct
19 Correct 232 ms 397256 KB Output is correct
20 Correct 235 ms 397136 KB Output is correct
21 Correct 228 ms 397200 KB Output is correct
22 Correct 229 ms 397124 KB Output is correct
23 Correct 235 ms 397140 KB Output is correct
24 Correct 236 ms 397136 KB Output is correct
25 Correct 237 ms 397156 KB Output is correct
26 Correct 233 ms 397136 KB Output is correct
27 Correct 246 ms 397396 KB Output is correct
28 Correct 232 ms 397260 KB Output is correct
29 Correct 233 ms 399184 KB Output is correct
30 Correct 368 ms 416852 KB Output is correct
31 Correct 413 ms 417360 KB Output is correct
32 Correct 391 ms 417364 KB Output is correct
33 Correct 428 ms 417032 KB Output is correct
34 Correct 414 ms 416748 KB Output is correct
35 Correct 444 ms 416852 KB Output is correct
36 Execution timed out 4058 ms 411192 KB Time limit exceeded
37 Halted 0 ms 0 KB -