Submission #569657

#	Time	Username	Problem	Language	Result	Execution time	Memory
569657		jamezzz	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1063 ms	100044 KiB

sprinkler

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 200005

int n,l,q,h[maxn],par[maxn];
ll mult[maxn][45]; //mult[i][j]: at node i, this thing can travel j more
vi AL[maxn];

void dfs(int u){
	for(int v:AL[u]){
		if(v==par[u])continue;
		par[v]=u;
		dfs(v);
	}
}

int main(){
	sf("%d%d",&n,&l);
	for(int i=0;i<n-1;++i){
		int a,b;sf("%d%d",&a,&b);
		AL[a].pb(b);
		AL[b].pb(a);
	}
	for(int i=1;i<=n;++i){
		sf("%d",&h[i]);
	}
	dfs(1);
	
	for(int i=0;i<=n;++i){
		for(int j=0;j<=41;++j){
			mult[i][j]=1;
		}
	}
	
	sf("%d",&q);
	while(q--){
		int t;sf("%d",&t);
		if(t==1){
			int x,d,w;sf("%d%d%d",&x,&d,&w);
			int cur=x;
			for(int i=d;i>=0;--i){
				mult[cur][i]*=w;
				mult[cur][i]%=l;
				if(par[cur]==0){
					for(int j=i-1;j>=0;--j){
						mult[cur][j]*=w;
						mult[cur][j]%=l;
					}
					break;
				}
				else cur=par[cur];
			}
			
			/*
			for(int i=1;i<=4;++i){
				pf("mult[%d]: ",i);
				for(int j=0;j<=4;++j){
					pf("%lld ",mult[i][j]);
				}
				pf("\n");
			}
			*/
		}
		else{
			int x;sf("%d",&x);
			ll ans=h[x];
			int cur=x,d=0;
			while(d<=40&&cur!=0){
				ans*=mult[cur][d];
				ans%=l;
				if(par[cur]!=0){
					ans*=mult[cur][d+1];
					ans%=l;
				}
				cur=par[cur];
				++d;
			}
			pf("%lld\n",ans);
		}
	}
}

/*
4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4
*/

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:61:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  sf("%d%d",&n,&l);
      |    ^
sprinkler.cpp:63:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   int a,b;sf("%d%d",&a,&b);
      |             ^
sprinkler.cpp:68:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   sf("%d",&h[i]);
      |     ^
sprinkler.cpp:78:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  sf("%d",&q);
      |    ^
sprinkler.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   int t;sf("%d",&t);
      |           ^
sprinkler.cpp:82:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    int x,d,w;sf("%d%d%d",&x,&d,&w);
      |                ^
sprinkler.cpp:108:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |    int x;sf("%d",&x);
      |            ^

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