oj.uz

Submission #550787

# Submission time Handle Problem Language Result Execution time Memory
550787 2022-04-19T08:21:40 Z inksamurai Sprinkler (JOI22_sprinkler) C++17
38 / 100
 1054 ms 98832 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3xxEYjy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

int mod;
//snuke's mod int
// template <ll mod>
struct modint{
	ll x; // typedef long long ll;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

signed main(){
_3xxEYjy;
	int n;
	cin>>n>>mod;
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1;v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	vi par;
	{
		rep(i,40){
			adj.pb({});
			if(i==0){
				adj[n].pb(0);
				adj[0].pb(n);
			}else{
				adj[n-1].pb(n);
				adj[n].pb(n-1);
			}
			n+=1;
		}
		par=vi(n,-1);
		auto dfs=[&](auto self,int v,int _par)->void{
			for(auto u:adj[v]){
				if(u==_par) continue;
				par[u]=v;
				self(self,u,v);
			}
		};dfs(dfs,n-1,-1);
		while(sz(a)<n){
			a.pb(0);
		}
	}

	using mint=modint;

	vec(vec(mint)) dp(n,vec(mint)(42,1));

	auto add=[&](int v,int d,int x){
		if(d==0){
			a[v]*=x%mod;
			a[v]%=mod;
			return;
		}
		while(1){
			if(v==-1) break;
			// print(v);
			if(d==0){
				a[v]*=x;
				a[v]%=mod;
				break;
			}
			dp[v][d]*=mint(x);
			d-=1;
			v=par[v];
		}
	};

	auto get=[&](int v)->mint{
		int d=0;
		mint res=1;
		while(d<40){
			res*=dp[v][d];
			res*=dp[v][d+1];
			v=par[v];
			if(v==-1) break;
			d+=1;
		}
		return res;
	};

	int q;
	cin>>q;
	rep(_,q){
		int t,v,x,d;
		cin>>t;
		if(t==1){
			cin>>v>>d>>x;
			v-=1;
			add(v,d,x);
		}else{
			cin>>v;
			v-=1;
			mint res=get(v);
			res*=mint(a[v]);
			print(res.x);
		}
	}	
//
	return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 3 ms 724 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 0 ms 340 KB Output is correct
2 Correct 734 ms 93040 KB Output is correct
3 Correct 449 ms 89564 KB Output is correct
4 Correct 727 ms 94776 KB Output is correct
5 Correct 650 ms 91376 KB Output is correct
6 Correct 484 ms 91236 KB Output is correct
7 Correct 466 ms 91692 KB Output is correct
8 Correct 395 ms 91940 KB Output is correct
9 Correct 958 ms 98832 KB Output is correct
10 Correct 543 ms 94780 KB Output is correct
11 Correct 810 ms 93212 KB Output is correct
12 Correct 493 ms 89640 KB Output is correct
13 Correct 280 ms 90004 KB Output is correct
14 Correct 309 ms 90112 KB Output is correct
15 Correct 295 ms 89956 KB Output is correct
16 Correct 300 ms 89844 KB Output is correct
17 Correct 369 ms 90456 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 324 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 734 ms 93040 KB Output is correct
3 Correct 449 ms 89564 KB Output is correct
4 Correct 727 ms 94776 KB Output is correct
5 Correct 650 ms 91376 KB Output is correct
6 Correct 484 ms 91236 KB Output is correct
7 Correct 466 ms 91692 KB Output is correct
8 Correct 395 ms 91940 KB Output is correct
9 Correct 958 ms 98832 KB Output is correct
10 Correct 543 ms 94780 KB Output is correct
11 Correct 810 ms 93212 KB Output is correct
12 Correct 493 ms 89640 KB Output is correct
13 Correct 280 ms 90004 KB Output is correct
14 Correct 309 ms 90112 KB Output is correct
15 Correct 295 ms 89956 KB Output is correct
16 Correct 300 ms 89844 KB Output is correct
17 Correct 369 ms 90456 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 324 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 320 KB Output is correct
24 Correct 813 ms 93152 KB Output is correct
25 Correct 502 ms 89596 KB Output is correct
26 Correct 732 ms 96700 KB Output is correct
27 Correct 610 ms 91388 KB Output is correct
28 Correct 509 ms 91504 KB Output is correct
29 Correct 474 ms 91532 KB Output is correct
30 Correct 406 ms 91820 KB Output is correct
31 Correct 972 ms 96852 KB Output is correct
32 Correct 461 ms 94780 KB Output is correct
33 Correct 799 ms 93104 KB Output is correct
34 Correct 431 ms 89656 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 2 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 984 ms 95944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1054 ms 96480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 3 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -