oj.uz

답안 #998455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998455 2024-06-14T02:23:46 Z efishel Sprinkler (JOI22_sprinkler) C++17
0 / 100
 298 ms 397308 KB 
//Sprinkler Saul
#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];

struct segtree{
	segtree *left, *right;
	int l, r, mid;
	ll v=1;
	segtree(int x=0, int y=lim): l(x), r(y){
		if(l==r) return;
		mid=((l+r)>>1);
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
	}
	void update(int x, int y, ll z){
		if(y<l || r<x) return;
		if(x<=l && r<=y){
			v*=z;
			v%=L;
			return;
		}
		left->update(x,y,z);
		right->update(x,y,z);
	}
	ll query(int x){
		if(x<l || r<x) return 1;
		if(x<=l && r<=x) return v;
		return (((left->query(x)*right->query(x))%L)*v)%L;
	}
} 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;
	queue<int> q;
	q.push(u);
	q.push(0);
	h[u][l]=0;
	while(q.size()){
		x=q.front();
		q.pop();
		d=q.front();
		q.pop();
		repa(y,adj[x]){
			if(h[y][lvl[u]]>d+1){
				h[y][lvl[u]]=d+1;
				q.push(y);
				q.push(d+1);
			}
		}
	}
	pos[u]=sum[l]+1;
	sum[l]+=d;
	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){
			H[x.fi]*=w;
			H[x.fi]%=L;
			//ST[lvl[u]].update(pos[u],pos[u]+max(pos[u],min(d-h[u][lvl[x.fi]],mx[u])),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,0,lim) rep(j,0,20) h[i][j]=1e9;
	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:132:8: warning: unused variable 'm' [-Wunused-variable]
  132 |  ll n, m, u, v;
      |        ^
sprinkler.cpp: In function 'void dis(int, int)':
sprinkler.cpp:79:7: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  mx[u]=d;
      |  ~~~~~^~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 265 ms 397284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 296 ms 397308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 296 ms 397308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 298 ms 397132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 292 ms 397292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 265 ms 397284 KB Output isn't correct
2 Halted 0 ms 0 KB -