oj.uz

Submission #999545

# Submission time Handle Problem Language Result Execution time Memory
999545 2024-06-15T18:26:30 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 1214 ms 123984 KB 
#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 {
    int n;
    vector<ll> tree;
    segtree() {
        n = lim;
        tree.assign(2 * n, 1);
    }
    void update(int l, int r, ll value) {
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) tree[l] = (tree[l] * value) % L, l++;
            if (r & 1) --r, tree[r] = (tree[r] * value) % L;
        }
    }
    ll query(int pos) {
        ll res = 1;
        for (pos += n; pos > 0; pos >>= 1) {
            res = (res * tree[pos]) % L;
        }
        return res;
    }
} 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);
		x={par[x.fi].fi,par[x.fi].se+x.se};
	}
	ST[lvl[u]].update(pos[u]+min((int)(d==2),mx[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;
}
 
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:124:8: warning: unused variable 'm' [-Wunused-variable]
  124 |  ll n, m, u, v;
      |        ^

Subtask #1
0 / 3.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 78684 KB Output is correct
2 Correct 678 ms 112544 KB Output is correct
3 Correct 443 ms 111440 KB Output is correct
4 Correct 914 ms 123984 KB Output is correct
5 Correct 542 ms 111788 KB Output is correct
6 Correct 436 ms 111528 KB Output is correct
7 Correct 420 ms 112264 KB Output is correct
8 Correct 236 ms 112724 KB Output is correct
9 Correct 1176 ms 121680 KB Output is correct
10 Correct 643 ms 120236 KB Output is correct
11 Correct 663 ms 111956 KB Output is correct
12 Correct 422 ms 111292 KB Output is correct
13 Correct 199 ms 112384 KB Output is correct
14 Correct 206 ms 112452 KB Output is correct
15 Correct 216 ms 112152 KB Output is correct
16 Correct 233 ms 111856 KB Output is correct
17 Correct 245 ms 112412 KB Output is correct
18 Correct 19 ms 78684 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct
20 Correct 21 ms 78680 KB Output is correct
21 Correct 19 ms 78836 KB Output is correct
22 Correct 19 ms 78680 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 78684 KB Output is correct
2 Correct 678 ms 112544 KB Output is correct
3 Correct 443 ms 111440 KB Output is correct
4 Correct 914 ms 123984 KB Output is correct
5 Correct 542 ms 111788 KB Output is correct
6 Correct 436 ms 111528 KB Output is correct
7 Correct 420 ms 112264 KB Output is correct
8 Correct 236 ms 112724 KB Output is correct
9 Correct 1176 ms 121680 KB Output is correct
10 Correct 643 ms 120236 KB Output is correct
11 Correct 663 ms 111956 KB Output is correct
12 Correct 422 ms 111292 KB Output is correct
13 Correct 199 ms 112384 KB Output is correct
14 Correct 206 ms 112452 KB Output is correct
15 Correct 216 ms 112152 KB Output is correct
16 Correct 233 ms 111856 KB Output is correct
17 Correct 245 ms 112412 KB Output is correct
18 Correct 19 ms 78684 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct
20 Correct 21 ms 78680 KB Output is correct
21 Correct 19 ms 78836 KB Output is correct
22 Correct 19 ms 78680 KB Output is correct
23 Correct 19 ms 78672 KB Output is correct
24 Incorrect 662 ms 111956 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 78676 KB Output is correct
2 Correct 1214 ms 117432 KB Output is correct
3 Correct 723 ms 123732 KB Output is correct
4 Correct 959 ms 119380 KB Output is correct
5 Correct 571 ms 109196 KB Output is correct
6 Correct 466 ms 109316 KB Output is correct
7 Correct 419 ms 109448 KB Output is correct
8 Correct 224 ms 109784 KB Output is correct
9 Correct 1170 ms 122028 KB Output is correct
10 Correct 704 ms 123008 KB Output is correct
11 Correct 661 ms 109020 KB Output is correct
12 Correct 520 ms 109388 KB Output is correct
13 Correct 332 ms 110420 KB Output is correct
14 Correct 326 ms 110620 KB Output is correct
15 Correct 21 ms 78684 KB Output is correct
16 Correct 19 ms 78724 KB Output is correct
17 Correct 18 ms 78660 KB Output is correct
18 Correct 20 ms 78684 KB Output is correct
19 Incorrect 19 ms 78684 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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