oj.uz

Submission #999546

# Submission time Handle Problem Language Result Execution time Memory
999546 2024-06-15T18:31:28 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 1308 ms 126932 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);
}
 
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:125:8: warning: unused variable 'm' [-Wunused-variable]
  125 |  ll n, m, u, v;
      |        ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78684 KB Output is correct
2 Correct 19 ms 78740 KB Output is correct
3 Correct 18 ms 78684 KB Output is correct
4 Incorrect 19 ms 78940 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 25 ms 78668 KB Output is correct
2 Correct 696 ms 105420 KB Output is correct
3 Correct 423 ms 101968 KB Output is correct
4 Correct 924 ms 116052 KB Output is correct
5 Correct 538 ms 103664 KB Output is correct
6 Correct 444 ms 103844 KB Output is correct
7 Correct 413 ms 104076 KB Output is correct
8 Correct 236 ms 104420 KB Output is correct
9 Correct 1178 ms 114768 KB Output is correct
10 Correct 645 ms 110672 KB Output is correct
11 Correct 718 ms 105164 KB Output is correct
12 Correct 432 ms 102044 KB Output is correct
13 Correct 191 ms 103764 KB Output is correct
14 Correct 228 ms 103420 KB Output is correct
15 Correct 213 ms 103060 KB Output is correct
16 Correct 229 ms 102904 KB Output is correct
17 Correct 256 ms 103324 KB Output is correct
18 Correct 19 ms 78832 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct
20 Correct 19 ms 78684 KB Output is correct
21 Correct 21 ms 78688 KB Output is correct
22 Correct 18 ms 78680 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 78668 KB Output is correct
2 Correct 696 ms 105420 KB Output is correct
3 Correct 423 ms 101968 KB Output is correct
4 Correct 924 ms 116052 KB Output is correct
5 Correct 538 ms 103664 KB Output is correct
6 Correct 444 ms 103844 KB Output is correct
7 Correct 413 ms 104076 KB Output is correct
8 Correct 236 ms 104420 KB Output is correct
9 Correct 1178 ms 114768 KB Output is correct
10 Correct 645 ms 110672 KB Output is correct
11 Correct 718 ms 105164 KB Output is correct
12 Correct 432 ms 102044 KB Output is correct
13 Correct 191 ms 103764 KB Output is correct
14 Correct 228 ms 103420 KB Output is correct
15 Correct 213 ms 103060 KB Output is correct
16 Correct 229 ms 102904 KB Output is correct
17 Correct 256 ms 103324 KB Output is correct
18 Correct 19 ms 78832 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct
20 Correct 19 ms 78684 KB Output is correct
21 Correct 21 ms 78688 KB Output is correct
22 Correct 18 ms 78680 KB Output is correct
23 Correct 18 ms 78684 KB Output is correct
24 Incorrect 637 ms 105180 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 78676 KB Output is correct
2 Incorrect 1173 ms 110932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78936 KB Output is correct
2 Incorrect 1308 ms 126932 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 78684 KB Output is correct
2 Correct 19 ms 78740 KB Output is correct
3 Correct 18 ms 78684 KB Output is correct
4 Incorrect 19 ms 78940 KB Output isn't correct
5 Halted 0 ms 0 KB -