oj.uz

Submission #998462

# Submission time Handle Problem Language Result Execution time Memory
998462 2024-06-14T02:35:29 Z efishel Sprinkler (JOI22_sprinkler) C++17
Compilation error
 0 ms 0 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[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][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,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 'void update(int, int, long long int)':
sprinkler.cpp:110:91: error: no matching function for call to 'max(long long int, const int&, long long int&)'
  110 |    ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][lvl[x.fi]],mx[x.fi])),w);
      |                                                                                           ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sprinkler.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:110:91: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  110 |    ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][lvl[x.fi]],mx[x.fi])),w);
      |                                                                                           ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sprinkler.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:110:91: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  110 |    ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][lvl[x.fi]],mx[x.fi])),w);
      |                                                                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sprinkler.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:110:91: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  110 |    ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][lvl[x.fi]],mx[x.fi])),w);
      |                                                                                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sprinkler.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:110:91: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  110 |    ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][lvl[x.fi]],mx[x.fi])),w);
      |                                                                                           ^
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:132:8: warning: unused variable 'm' [-Wunused-variable]
  132 |  ll n, m, u, v;
      |        ^