oj.uz

Submission #999496

# Submission time Handle Problem Language Result Execution time Memory
999496 2024-06-15T15:50:04 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
21 / 100
 1263 ms 125340 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],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 20 ms 78672 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 24 ms 78760 KB Output is correct
2 Correct 703 ms 105296 KB Output is correct
3 Correct 439 ms 101972 KB Output is correct
4 Correct 1046 ms 116060 KB Output is correct
5 Correct 561 ms 103664 KB Output is correct
6 Correct 456 ms 103676 KB Output is correct
7 Correct 378 ms 104156 KB Output is correct
8 Correct 247 ms 104412 KB Output is correct
9 Correct 1171 ms 115540 KB Output is correct
10 Correct 668 ms 122540 KB Output is correct
11 Correct 704 ms 113492 KB Output is correct
12 Correct 417 ms 114004 KB Output is correct
13 Correct 229 ms 114756 KB Output is correct
14 Correct 208 ms 115452 KB Output is correct
15 Correct 225 ms 114488 KB Output is correct
16 Correct 250 ms 114632 KB Output is correct
17 Correct 275 ms 115184 KB Output is correct
18 Correct 21 ms 78684 KB Output is correct
19 Correct 20 ms 78672 KB Output is correct
20 Correct 24 ms 78684 KB Output is correct
21 Correct 20 ms 78844 KB Output is correct
22 Correct 21 ms 78676 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 78760 KB Output is correct
2 Correct 703 ms 105296 KB Output is correct
3 Correct 439 ms 101972 KB Output is correct
4 Correct 1046 ms 116060 KB Output is correct
5 Correct 561 ms 103664 KB Output is correct
6 Correct 456 ms 103676 KB Output is correct
7 Correct 378 ms 104156 KB Output is correct
8 Correct 247 ms 104412 KB Output is correct
9 Correct 1171 ms 115540 KB Output is correct
10 Correct 668 ms 122540 KB Output is correct
11 Correct 704 ms 113492 KB Output is correct
12 Correct 417 ms 114004 KB Output is correct
13 Correct 229 ms 114756 KB Output is correct
14 Correct 208 ms 115452 KB Output is correct
15 Correct 225 ms 114488 KB Output is correct
16 Correct 250 ms 114632 KB Output is correct
17 Correct 275 ms 115184 KB Output is correct
18 Correct 21 ms 78684 KB Output is correct
19 Correct 20 ms 78672 KB Output is correct
20 Correct 24 ms 78684 KB Output is correct
21 Correct 20 ms 78844 KB Output is correct
22 Correct 21 ms 78676 KB Output is correct
23 Correct 18 ms 78816 KB Output is correct
24 Incorrect 648 ms 113372 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78684 KB Output is correct
2 Correct 1210 ms 111776 KB Output is correct
3 Correct 723 ms 125340 KB Output is correct
4 Correct 1031 ms 120960 KB Output is correct
5 Correct 588 ms 110672 KB Output is correct
6 Correct 468 ms 110852 KB Output is correct
7 Correct 410 ms 111240 KB Output is correct
8 Correct 280 ms 111700 KB Output is correct
9 Correct 1263 ms 123732 KB Output is correct
10 Correct 753 ms 124916 KB Output is correct
11 Correct 697 ms 110336 KB Output is correct
12 Correct 527 ms 111440 KB Output is correct
13 Correct 378 ms 112212 KB Output is correct
14 Correct 328 ms 112720 KB Output is correct
15 Correct 20 ms 78684 KB Output is correct
16 Correct 19 ms 78684 KB Output is correct
17 Correct 22 ms 78844 KB Output is correct
18 Correct 19 ms 78684 KB Output is correct
19 Correct 19 ms 78684 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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