Submission #568311

#	Time	Username	Problem	Language	Result	Execution time	Memory
568311		jamielim	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1113 ms	113616 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,q;
ll l;
vector<int> adj[200005];
int h[200005];
int par[20][200005];
ll mult[200005][45];

void dfs(int x,int p){
	par[0][x]=p;
	for(int i:adj[x]){
		if(i==p)continue;
		dfs(i,x);
	}
}

int main(){
	scanf("%d%lld",&n,&l);
	int a,b;
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		adj[a].pb(b);adj[b].pb(a);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
	}
	dfs(1,0);
	for(int i=1;i<20;i++){
		for(int j=1;j<=n;j++){
			par[i][j]=par[i-1][par[i-1][j]];
		}
	}
	for(int i=0;i<=n;i++)for(int j=0;j<45;j++)mult[i][j]=1;
	
	scanf("%d",&q);
	int t,x,d,w;
	while(q--){
		scanf("%d%d",&t,&x);
		if(t==1){
			scanf("%d%d",&d,&w);
			int cur=x;
			for(int i=0;i<=d;i++){
				mult[cur][d-i]*=w;
				mult[cur][d-i]%=l;
				if(d-i-1>=0){
					mult[cur][d-i-1]*=w;
					mult[cur][d-i-1]%=l;
				}
				if(par[0][cur]==0){
					for(int j=d-i-2;j>=0;j--){
						mult[cur][j]*=w;
						mult[cur][j]%=l;
					}
					break;
				}
				cur=par[0][cur];
			}
		}else{
			ll ans=(h[x]*mult[x][0])%l;
			int cur=x;
			for(int i=1;i<=40;i++){
				cur=par[0][cur];
				if(cur==0)break;
				ans*=mult[cur][i];
				ans%=l;
			}
			printf("%lld\n",(ans+l)%l);
		}
	}
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%lld",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d",&h[i]);
      |   ~~~~~^~~~~~~~~~~~
sprinkler.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
sprinkler.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d",&t,&x);
      |   ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |    scanf("%d%d",&d,&w);
      |    ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17