Submission #854363

#	Time	Username	Problem	Language	Result	Execution time	Memory
854363		MilosMilutinovic	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	651 ms	68144 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> B;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=200200;
int n,q,l,f[N][45],h[N],p[N];
VI g[N];

int ckmul(int a,int b) { return ((ll)a*b)%l; }

void dfs(int x,int pv) {
	p[x]=pv;
	rep(i,0,42) f[x][i]=1;
	for (int y:g[x]) if (y!=pv) dfs(y,x);
}

void add(int x,int d,int w) {
	per(i,0,d+1) {
		f[x][i]=ckmul(f[x][i],w);
		if (i>0&&x!=1) f[x][i-1]=ckmul(f[x][i-1],w);
		x=p[x];
	}
}

int solve(int x) {
	int r=1;
	rep(i,0,42) {
		r=ckmul(r,f[x][i]);
		if (x==1) break;
		x=p[x];
	}
	return r;
}

int main() {
	scanf("%d%d",&n,&l);
	rep(i,1,n) {
		int a,b;
		scanf("%d%d",&a,&b);
		g[a].pb(b); g[b].pb(a);
	}
	rep(i,1,n+1) scanf("%d",&h[i]);
	dfs(1,1);
	rep(i,1,n+1) add(i,0,h[i]);
	scanf("%d",&q);
	while (q--) {
		int op;
		scanf("%d",&op);
		if (op==1) {
			int x,d,w;
			scanf("%d%d%d",&x,&d,&w);
			add(x,d,w);
		} else {
			int x;
			scanf("%d",&x);
			printf("%d\n",solve(x));
		}
	}
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:61:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  rep(i,1,n+1) scanf("%d",&h[i]);
      |               ~~~~~^~~~~~~~~~~~
sprinkler.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
sprinkler.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d",&op);
      |   ~~~~~^~~~~~~~~~
sprinkler.cpp:70:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |    scanf("%d%d%d",&x,&d,&w);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |    scanf("%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