Submission #1209129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209129		aaron_dcoder	Sprinkler (JOI22_sprinkler)	C++20	3 / 100	4098 ms	181944 KiB

sprinkler

/*
I QUIT
😭
*/
#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;

/*struct segtree
{
	vector<ll> toadd;
	segtree(ll n)
	{
		toadd.assign(4*n,0);
	}

	ll get(ll x, ll lseg, ll rseg, ll node)
	{
		if (x<lseg||x>rseg) return 0;
		return toadd[node]
	}
}*/

ll N,L;
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]];
			}
		}
	}*/

		


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


	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})
						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})
				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})
				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;
		}
		else if (t==2)
		{
			ll Xi;
			cin >> Xi;
			Xi--;//c
			cout << H[posn[Xi]] << "\n";
		}
		else throw exception();
	}

}

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