oj.uz

Submission #999551

# Submission time Handle Problem Language Result Execution time Memory
999551 2024-06-15T18:45:20 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 1174 ms 118836 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};
	}
	if(d<=1) ST[lvl[u]].update(pos[u],pos[u]+min(d,mx[u]),w);
	else{
		if(mx[u]) ST[lvl[u]].update(pos[u]+1,pos[u]+min(d,mx[u]),w);
		if(!lvl[u]) H[u]=(H[u]*w)%L;
	}
}
 
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:128:8: warning: unused variable 'm' [-Wunused-variable]
  128 |  ll n, m, u, v;
      |        ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78672 KB Output is correct
2 Correct 19 ms 78680 KB Output is correct
3 Correct 18 ms 78684 KB Output is correct
4 Incorrect 21 ms 78896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 78684 KB Output is correct
2 Correct 582 ms 105296 KB Output is correct
3 Correct 438 ms 101968 KB Output is correct
4 Correct 929 ms 116036 KB Output is correct
5 Correct 561 ms 103644 KB Output is correct
6 Correct 423 ms 103672 KB Output is correct
7 Correct 399 ms 104076 KB Output is correct
8 Correct 241 ms 104372 KB Output is correct
9 Correct 1112 ms 114772 KB Output is correct
10 Correct 627 ms 110676 KB Output is correct
11 Correct 660 ms 105208 KB Output is correct
12 Correct 421 ms 101968 KB Output is correct
13 Correct 197 ms 103620 KB Output is correct
14 Correct 201 ms 103468 KB Output is correct
15 Correct 222 ms 103088 KB Output is correct
16 Correct 233 ms 102864 KB Output is correct
17 Correct 268 ms 103356 KB Output is correct
18 Correct 20 ms 78680 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct
20 Correct 19 ms 78684 KB Output is correct
21 Correct 20 ms 78684 KB Output is correct
22 Correct 21 ms 78680 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 78684 KB Output is correct
2 Correct 582 ms 105296 KB Output is correct
3 Correct 438 ms 101968 KB Output is correct
4 Correct 929 ms 116036 KB Output is correct
5 Correct 561 ms 103644 KB Output is correct
6 Correct 423 ms 103672 KB Output is correct
7 Correct 399 ms 104076 KB Output is correct
8 Correct 241 ms 104372 KB Output is correct
9 Correct 1112 ms 114772 KB Output is correct
10 Correct 627 ms 110676 KB Output is correct
11 Correct 660 ms 105208 KB Output is correct
12 Correct 421 ms 101968 KB Output is correct
13 Correct 197 ms 103620 KB Output is correct
14 Correct 201 ms 103468 KB Output is correct
15 Correct 222 ms 103088 KB Output is correct
16 Correct 233 ms 102864 KB Output is correct
17 Correct 268 ms 103356 KB Output is correct
18 Correct 20 ms 78680 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct
20 Correct 19 ms 78684 KB Output is correct
21 Correct 20 ms 78684 KB Output is correct
22 Correct 21 ms 78680 KB Output is correct
23 Correct 20 ms 78684 KB Output is correct
24 Incorrect 635 ms 105556 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78684 KB Output is correct
2 Incorrect 1127 ms 110912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 78672 KB Output is correct
2 Incorrect 1174 ms 118836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78672 KB Output is correct
2 Correct 19 ms 78680 KB Output is correct
3 Correct 18 ms 78684 KB Output is correct
4 Incorrect 21 ms 78896 KB Output isn't correct
5 Halted 0 ms 0 KB -