oj.uz

Submission #999547

# Submission time Handle Problem Language Result Execution time Memory
999547 2024-06-15T18:34:17 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 1246 ms 118680 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]+(par[u].fi>0),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 78680 KB Output is correct
2 Correct 18 ms 78684 KB Output is correct
3 Correct 19 ms 78680 KB Output is correct
4 Incorrect 21 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 19 ms 78684 KB Output is correct
2 Correct 664 ms 105304 KB Output is correct
3 Correct 406 ms 101968 KB Output is correct
4 Correct 974 ms 116052 KB Output is correct
5 Correct 509 ms 103768 KB Output is correct
6 Correct 467 ms 103676 KB Output is correct
7 Correct 402 ms 104076 KB Output is correct
8 Correct 237 ms 104420 KB Output is correct
9 Correct 1183 ms 114768 KB Output is correct
10 Correct 629 ms 110788 KB Output is correct
11 Correct 692 ms 105448 KB Output is correct
12 Correct 436 ms 101964 KB Output is correct
13 Correct 193 ms 103768 KB Output is correct
14 Correct 198 ms 103416 KB Output is correct
15 Correct 219 ms 103168 KB Output is correct
16 Correct 363 ms 102992 KB Output is correct
17 Correct 236 ms 103276 KB Output is correct
18 Correct 25 ms 78832 KB Output is correct
19 Correct 20 ms 78684 KB Output is correct
20 Correct 20 ms 78684 KB Output is correct
21 Correct 19 ms 78684 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 19 ms 78684 KB Output is correct
2 Correct 664 ms 105304 KB Output is correct
3 Correct 406 ms 101968 KB Output is correct
4 Correct 974 ms 116052 KB Output is correct
5 Correct 509 ms 103768 KB Output is correct
6 Correct 467 ms 103676 KB Output is correct
7 Correct 402 ms 104076 KB Output is correct
8 Correct 237 ms 104420 KB Output is correct
9 Correct 1183 ms 114768 KB Output is correct
10 Correct 629 ms 110788 KB Output is correct
11 Correct 692 ms 105448 KB Output is correct
12 Correct 436 ms 101964 KB Output is correct
13 Correct 193 ms 103768 KB Output is correct
14 Correct 198 ms 103416 KB Output is correct
15 Correct 219 ms 103168 KB Output is correct
16 Correct 363 ms 102992 KB Output is correct
17 Correct 236 ms 103276 KB Output is correct
18 Correct 25 ms 78832 KB Output is correct
19 Correct 20 ms 78684 KB Output is correct
20 Correct 20 ms 78684 KB Output is correct
21 Correct 19 ms 78684 KB Output is correct
22 Correct 19 ms 78680 KB Output is correct
23 Correct 23 ms 78684 KB Output is correct
24 Incorrect 656 ms 105348 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 78680 KB Output is correct
2 Incorrect 1127 ms 111112 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 78680 KB Output is correct
2 Incorrect 1246 ms 118680 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 78680 KB Output is correct
2 Correct 18 ms 78684 KB Output is correct
3 Correct 19 ms 78680 KB Output is correct
4 Incorrect 21 ms 78940 KB Output isn't correct
5 Halted 0 ms 0 KB -