Submission #1131092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131092		Math4Life2020	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	1693 ms	426552 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

typedef unsigned long long ull;
typedef __uint128_t LLL;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((LLL(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((LLL(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod B(2);

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

ll get(ll x, ll dht) {
	if (dht >= Dm) {
		return 1;
	}
	return pdn[x][dht];
}

void cnstr(ll x, vector<ll> vf) { //x = memory location, vf = things to eventually point to
	if (vf.size()<=2) {
		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 (x>=N) {
		if (pdn[x][d]==1) return;
		for (ll y: fadj2[x]) {
			pdn[y][d]=B.reduce(pdn[y][d]*pdn[x][d]);
		}
		pdn[x][d]=1;
	} else {
		if (pdn[x][d]==1) return;
		for (ll y: fadj2[x]) {
			pdn[y][d-1]=B.reduce(pdn[y][d-1]*pdn[x][d]);
		}
		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;
	B = FastMod(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;
	ll mdp = 0;
	for (ll q=0;q<Q;q++) {
		ll Tk; cin >> Tk;
		if (Tk==1) {
			ll x0,d0,w0; cin >> x0 >> d0 >> w0;
			mdp = max(mdp,d0);
			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;
			ll ans = H0[x0];
			for (ll d=0;d<=Dm;d++) {
				ans = B.reduce(ans*get(xrev,ht[x0]-ht[xrev]));
				if (radj[xrev]!=-1) {
					xrev = radj[xrev];
				} else {
					break;
				}
			}
			cout << ans << "\n";
		}
	} 
}

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