Submission #589272

#	Time	Username	Problem	Language	Result	Execution time	Memory
589272		Tekor	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4067 ms	110800 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define f first
#define s second
#define pii pair <int,int>
#define en '\n'
#define all(v) v.begin(),v.end()
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 4e5 + 100;
const int bl = 400;
vector <int> g[N];
ll a[N],L;
int h[N],tin[N],tout[N],Tima,pr[N],mxh;
int n,k[N];
vector <ll> t[N],t1[N];
vector <int> q[N];
void dfs_build(int v,int p) {
	tin[v] = ++Tima;
	q[h[v]].pb(tin[v]);
	for(auto to : g[v]) {
		if(to == p)continue;
		h[to] = h[v] + 1;
		pr[to] = v;
		dfs_build(to,v);
	}
	tout[v] = Tima;
}
void push(int d,int v) {
	t[d][v + v] = (t[d][v + v] * t1[d][v]) % L;
	t[d][v + v + 1] = (t[d][v + v + 1] * t1[d][v]) % L;
	t1[d][v + v] = (t1[d][v + v] * t1[d][v]) % L;
	t1[d][v + v + 1] = (t1[d][v + v + 1] * t1[d][v]) % L;
	t1[d][v] = 1;
}
void upd(int d,int v,int tl,int tr,int l,int r,ll x) {
	if(q[d][tl] > r || q[d][tr] < l)return;
	if(q[d][tl] >= l && q[d][tr] <= r) {
		t1[d][v] = (t1[d][v] * x) % L;
		t[d][v] = (t[d][v] * x) % L;
		return;
	}
	push(d,v);
	int tm = (tl + tr) / 2;
	upd(d,v + v,tl,tm,l,r,x);
	upd(d,v + v + 1,tm + 1,tr,l,r,x);
}
ll get(int d,int v,int tl,int tr,int pos) {
	//cout << v << " " << tl << " " << tr << endl;
	if(tl == tr)return t[d][v];
	push(d,v);
	int tm = (tl + tr) / 2;
	if(q[d][tm] >= pos)return get(d,v + v,tl,tm,pos);
	else return get(d,v + v + 1,tm + 1,tr,pos);
}
void build() {
	for(int i = 1;i <= n;i++) {
		if(q[i].empty())break;
		k[i] = q[i].size();
		q[i].pb(0);
		sort(all(q[i]));
		for(int j = 0;j <= 4 * k[i];j++) {
			t[i].pb(1);
			t1[i].pb(1);
		}
		mxh = i;
	}
}
void add(int x,int dist,ll w) {
	int v = x;
	int tek = 0;
	while(tek <= dist) {
		int need = h[v] + dist - tek;
		if(need <= mxh)upd(need,1,1,k[need],tin[v],tout[v],w);
		if(x == 4) {
			//cout << need << " ";
		}
		if(dist - tek > 0 && pr[v] != -1) {
			need--;
			//cout << need << " ";
			if(need <= mxh)upd(need,1,1,k[need],tin[v],tout[v],w);
		}
		if(pr[v] != -1)v = pr[v];
		tek++;
	}
}
ll getans(int pos) {
	//cout << h[pos] << " " << k[h[pos]] << endl;
	ll val = get(h[pos],1,1,k[h[pos]],tin[pos]);
	//cout << val << endl;
	return (val * a[pos]) % L;
}
void solve() {
	cin >> n >> L;
	for(int i = 1;i <= n;i++) {
		pr[i] = -1;
	}
	for(int i = 1;i < n;i++) {
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i = 1;i <= n;i++)cin >> a[i];
	h[1] = 1;
	dfs_build(1,-1);
	build();
	int m;
	cin >> m;
	for(int i = 1;i <= m;i++) {
		int typ;
		cin >> typ;
		if(typ == 1) {
			int x,dist;
			ll w;
			cin >> x >> dist >> w;
			add(x,dist,w);
		}else {
			int x;
			cin >> x;
			cout << getans(x) << en;
		}
	}
}

int main() {
	boos();
	int ttt;
	ttt = 1;
	while(ttt--) {
		solve();
	}
}

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