Submission #1131081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131081		Math4Life2020	Sprinkler (JOI22_sprinkler)	C++20	3 / 100	4120 ms	419504 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e6+5;
const ll Dm = 41; 
vector<ll> pr;
ll N,L;
vector<ll> adj[Nm];
ll radj[Nm];
vector<ll> fadj[Nm];
vector<ll> fadj2[Nm];
ll radj2[Nm];
ll ht[Nm];
ll IMEM; //memory index (for new allocation)
ll pdn[Nm][Dm]; //at vertex x: push down exactly distance d

void wt(ll x, ll d, ll w) { //current x, distance left, # to multiply
	assert(d>=0);
	if (d==0) {
		pdn[x][0]=pdn[x][0]*w;
		pdn[x][0]=pdn[x][0]%L;
		return;
	}
	if (radj[x]==-1) {
		for (ll k=0;k<=d;k++) {
			pdn[x][k]=pdn[x][k]*w;
			pdn[x][k]=pdn[x][k]%L;
		}
		return;
	} else {
		pdn[x][d]=pdn[x][d]*w;
		pdn[x][d-1]=pdn[x][d-1]*w;
		pdn[x][d]=pdn[x][d]%L;
		pdn[x][d-1]=pdn[x][d-1]%L;
		wt(radj[x],d-1,w);
	}
}

void cnstr(ll x, vector<ll> vf) { //x = memory location, vf = things to eventually point to
	if (vf.size()<=3) {
		for (ll y: vf) {
			fadj2[x].push_back(y);
			radj2[y]=x;
		}
	} else {
		vector<ll> vf1,vf2;
		ll M = vf.size();
		for (ll i=0;i<(M/2);i++) {
			vf1.push_back(vf[i]);
		}
		for (ll i=(M/2);i<M;i++) {
			vf2.push_back(vf[i]);
		}
		fadj2[x].push_back(IMEM);
		radj2[IMEM]=x;
		if (x<N) {
			ht[IMEM]=ht[x]+1;
		} else {
			ht[IMEM]=ht[x];
		}
		cnstr(IMEM++,vf1);

		fadj2[x].push_back(IMEM);
		radj2[IMEM]=x;
		if (x<N) {
			ht[IMEM]=ht[x]+1;
		} else {
			ht[IMEM]=ht[x];
		}
		cnstr(IMEM++,vf2);
	}
}

void psh(ll x, ll hf) {
	/*ll d = hf-ht[x];
	if (d>=Dm) {
		return;
	}
	for (ll y: fadj2[x]) {
		if (x>=N) {
			{
				pdn[y][d]=(pdn[y][d]*pdn[x][d])%L;
			}
		} else {
			{
				pdn[y][d-1]=(pdn[y][d-1]*pdn[x][d])%L;
			}
		}
	}
	if (x>=N) {
		pdn[x][d]=1;
	} else {
		pdn[x][d]=1;
	}*/
	ll d = hf-ht[x];
	if (x>=N) {
		for (ll y: fadj2[x]) {
			pdn[y][d]=(pdn[y][d]*pdn[x][d])%L;
		}
		pdn[x][d]=1;
	} else {
		for (ll y: fadj2[x]) {
			pdn[y][d-1]=(pdn[y][d-1]*pdn[x][d])%L;
		}
		pdn[x][d]=1;
	}
}

int main() {
	for (ll i=0;i<Nm;i++) {
		for (ll j=0;j<Dm;j++) {
			pdn[i][j]=1;
		}
	}
	cin >> N >> L;
	ll H0[N];
	IMEM = N;
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b; a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	radj[0]=-1;
	ht[0]=0;
	queue<ll> q0; q0.push(0);
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		for (ll y: adj[x]) {
			if (y != radj[x]) {
				radj[y]=x;
				fadj[x].push_back(y);
				ht[y]=1+ht[x];
				q0.push(y);
			}
		}
	}
	for (ll x=0;x<N;x++) {
		cnstr(x,fadj[x]); //create fadj2
		cin >> H0[x];
	}
	radj2[0]=-1;
	ll Q; cin >> Q;
	for (ll q=0;q<Q;q++) {
		ll Tk; cin >> Tk;
		if (Tk==1) {
			ll x0,d0,w0; cin >> x0 >> d0 >> w0;
			x0--;
			//cout << "x,d,w="<<x0<<","<<d0<<","<<w0<<"\n"; exit(0);
			wt(x0,d0,w0); //write
		} else {
			ll x0; cin >> x0; x0--;
			ll xrev = x0;
			for (ll d=0;d<(Dm-1);d++) {
				if (radj[xrev]!=-1) {
					xrev = radj[xrev];
				}
			}
			vector<ll> xupd; 
			ll xc = x0;
			while(1) {
				xupd.push_back(xc);
				if (xc != xrev) {
					xc = radj2[xc];
				} else {
					break;
				}
			}
			assert(xupd.size()<=800);
			for (ll i=(xupd.size()-1);i>=1;i--) {
				psh(xupd[i],ht[x0]);
			}
			ll ans = pdn[x0][0];
			ans = (ans*H0[x0])%L;
			cout << ans << "\n";
		}
	} 
}

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