Submission #1209143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209143		aaron_dcoder	Sprinkler (JOI22_sprinkler)	C++20	41 / 100	4098 ms	186696 KiB

sprinkler

/*
I QUIT
😭
NEVEER!!!!
*/
#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>

using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

ll N,L;


struct segtree
{
	vector<ll> tomul;
	segtree(ll n)
	{
		tomul.assign(4*n,1);
	}

	ll get(ll x, ll l, ll r, ll node)
	{
		if (x<l||x>r) return 1;
		if (l==r && l==x) return tomul[node];
		ll mid = (l+r)/2;
		return (tomul[node] * get(x,l,mid,node*2) * get(x,mid+1,r,node*2+1))%L;
	}

	void mul(ll val, ll lseg, ll rseg, ll l, ll r, ll node)
	{
	//	dbgv(lseg);dbgv(rseg);dbgv(l);dbgv(r);dbgv(node);
		if (lseg>r||rseg<l) return;
		if (lseg<=l && r<=rseg)
		{
			tomul[node]*=val;
			tomul[node]%=L;
			return;
		}
		ll mid = (l+r)/2;
		mul(val, lseg, rseg, l,mid, node*2);
		mul(val, lseg, rseg, mid+1,r , node*2+1);
	}

};

vector<vector<ll>> tree;

vector<vector<ll>> children;
vector<ll> parent;

array<vector<ll>, 42> binright;
array<vector<ll>, 42> binleft;

vector<ll> dfsstack;

void dfs(ll node)
{
	dfsstack.push_back(node);
	for (ll child : tree[node])
	{
		if (child==parent[node]) continue;
		children[node].push_back(child);
		parent[child]=node;
		dfs(child);
	}
	/*if (ll(dfsstack.size())>3 && dfsstack[ll(dfsstack.size()) - 3]==536)
	{
		dbgv("huh");
		dbgv(node);
	}*/
	for (ll p = 0; p<42 && (ll(dfsstack.size()) - 1 - p)>=0; ++p)
	{
		ll ancnode = dfsstack[ll(dfsstack.size()) - 1 - p];
		if (binleft[p][ancnode]==-1)
		{
			binleft[p][ancnode]=node;
		}
		binright[p][ancnode]=node;
	}
	dfsstack.pop_back();
}

vector<ll> posn;

pll getdescendent(ll node, ll d)
{
	/*ll l = node;
	ll r = node;
	for (ll p = 0; (1ll<<p)<=d; ++p)
	{
		//dbgv(l);dbgv(r);dbgv(p);
		if (((d>>p)&1ll) == 1)
		{
			l = binleft[p][l];
			r = binright[p][r];
		}
		if (l==-1 || r==-1)
		{
			dbgv(node);
			dbgv(d);
			dbgv(r);
			return {-1,-1};
		}
	}
	for (ll i = 0; i < d; ++i)
	{
		l = binleft[0][l];
		r = binright[0][r];
		if (l==-1 || r==-1)
		{
			dbgv(node);
			dbgv(d);
			dbgv(r);
			return {-1,-1};
		}
	}
	if (posn[l]<=posn[r]) return {l,r};
	else return {-1,-1};*/
	assert(!((binleft[d][node]==-1)^(binright[d][node]==-1)));
	return {binleft[d][node],binright[d][node]};
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	dbgv("Started");

	cin >> N >> L;

	tree.assign(N,{});

	for (ll i = 0; i < N-1; ++i)
	{
		ll a,b;
		cin >> a >> b;
		a--; b--; //c
		tree[a].push_back(b);
		tree[b].push_back(a);	
	}


	children.assign(N,{});
	parent.assign(N,-1);
	binleft.fill(vector<ll>(N,-1));
	binright.fill(vector<ll>(N,-1));

	dfs(0);


	ll currposn = 0;
	posn.assign(N,-1);
	queue<ll> bfsq;
	bfsq.push(0);
	while (!bfsq.empty())
	{
		ll curr=bfsq.front();
		bfsq.pop();
		posn[curr] = currposn++;
		for (ll child:children[curr])
		{
			bfsq.push(child);
		}
	}

	/*for (ll p = 0; p<25; p++)
	{
		for (ll i = 1; i < N; ++i)
		{
			if (binright[p][posn[i]]==-1)
			{
				binright[p][posn[i]] = binright[p][posn[i-1]];
			}
		}
		for (ll i = N-2; i >=0; --i)
		{
			if (binleft[p][posn[i]]==-1)
			{
				binleft[p][posn[i]] = binleft[p][posn[i+1]];
			}
		}
	}*/

		
dbgv("p0 done");

	segtree H(N);
	for (ll i = 0; i < N; ++i)
	{
		ll Hi;
		cin >> Hi;
		H.mul(Hi,posn[i],posn[i], 0,N-1,1);
	}

	dbgv("p1 done");

	ll Q;
	cin >> Q;
	for (ll qno = 0; qno < Q; ++qno)
	{
		/*dbgv(qno);
		dbgfor (ll i = 0; i < N; ++i)
		{
			cerr << (H[posn[i]]) << " ";
		}*/
		ll t;
		cin >> t;
		if (t==1)
		{
			ll Xi,Di,Wi;
			cin >> Xi >> Di >> Wi;
			Xi--;//c
			ll currn = Xi;
			for (ll h = 0; h < Di; ++h)
			{
				//dbgv(currn+1);
				if (currn==0)
				{
					for (ll d = 1; d <= Di-h; ++d)
					{
						pll r1 = getdescendent(currn,d);
						if (r1!=pll{-1,-1})
						{
							H.mul(Wi,posn[r1.e0],posn[r1.e1], 0,N-1,1);
						}
						/*for (ll i = posn[r1.e0]; i <= posn[r1.e1]; ++i)
						{
							H[i] *= Wi;
							H[i] %= L;
						}*/
					}
					break;
				}

				pll r = getdescendent(currn,Di-h);
				if (r!=pll{-1,-1})
					{
							H.mul(Wi,posn[r.e0],posn[r.e1], 0,N-1,1);
						}

				/*for (ll i = posn[r.e0]; i <= posn[r.e1]; ++i)
				{
					H[i] *= Wi;
					H[i] %= L;
				}*/
				r = getdescendent(currn,Di-h-1);
				if (r!=pll{-1,-1})
					{
							H.mul(Wi,posn[r.e0],posn[r.e1], 0,N-1,1);
						}
				/*for (ll i = posn[r.e0]; i <= posn[r.e1]; ++i)
				{
					H[i] *= Wi;
					H[i] %= L;
				}*/
				currn=parent[currn];
				assert(currn>=0);
			}
			//dbgv(currn+1);
			/*H[posn[currn]] *= Wi;
			H[posn[currn]] %= L;*/
			{
				H.mul(Wi,posn[currn],posn[currn], 0,N-1,1);
			}
		}
		else if (t==2)
		{
			ll Xi;
			cin >> Xi;
			Xi--;//c
			cout << H.get(posn[Xi], 0,N-1,1) << "\n";
		}
		else throw exception();
	}

}

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