제출 #588866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588866		LastRonin	Sprinkler (JOI22_sprinkler)	C++14	12 / 100	1320 ms	125120 KiB

sprinkler

#pragma GCC optimize("O3")

#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 2e5 + 11;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;

mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());

ll n, L, q;
vector<ll> g[N];
ll sz[N];
ll h[N];
int lay[N];
ll dist[N][20];
ll cp[N];// centroid predok
bool del[N];

void dfs(ll v, ll p) {
	sz[v] = 1;
	for(auto u : g[v]) {
		if(p == u || del[u])continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}

void bdfs(ll v, ll p, ll k) {
	cp[v] = k;
	if(p == k)dist[v][lay[k]] = 1;
	else dist[v][lay[k]] = dist[p][lay[k]] + 1;
	for(auto u : g[v]) {
		if(u == p || del[u])continue;
		bdfs(u, v, k);
	}
}

int fnd(int v) {
	int p = 0;
	int siz = sz[v];
	while(p != v) {
		int c = v;
		for(auto u : g[c]) {
			if(u != p && !del[u] && sz[u] * 2ll > siz) {
				v = u;
				break;
			}
		}
		p = c;
	}
	return v;
}

void build(ll v, ll layer = 0) {
	dfs(v, 0);
	v = fnd(v);
	del[v] = 1;
	lay[v] = layer;
	for(auto u : g[v]) {
		if(!del[u])
			bdfs(u, v, v);	          	
	}
	for(auto u : g[v]) {
		if(!del[u]) {
			build(u, layer + 1);
		}
	}
}

int stp[N][41];
int per[N][41];
int als1[N], als2[N];

void add1(ll v, ll z) {
	als1[v]++;
	for(int j = z; j <= 40; j |= (j + 1))
		stp[v][j]++;				
}
void add2(ll v, ll z) {
	als2[v]++;
	for(int j = z; j <= 40; j |= (j + 1))
		per[v][j]++;				
}
ll get1(ll v, ll z) {
	if(z >= 40)return als1[v];	
	ll sum = 0;
	for(int j = z; j >= 0; j = (j & (j + 1)) - 1)
		sum = sum + stp[v][j];			
	return sum;
}
ll get2(ll v, ll z) {	
	if(z >= 40)return als2[v];	
	ll sum = 0;
	for(int j = z; j >= 0; j = (j & (j + 1)) - 1)
		sum = sum + per[v][j];			
	return sum;
}



void upd(ll a, ll c, ll b) {
	ll dis = 0;
	ll izn = a;
	int cnt = 0;
	add1(a, c);
	while(a) {
		if(cp[a] == 0)break;
		cnt++;
		assert(cnt <= 40);
		dis = dist[izn][lay[cp[a]]];
		if(c - dis >= 0) {
			add1(cp[a], c - dis);
			add2(a, c - dis);
		}				
		a = cp[a];
	}
}

ll getans(ll a) {
	ll dis = 0;
	ll izn = a;
	ll ans = als1[a];
	ll pr = a;
	a = cp[a];
	while(a) {
		dis = dist[izn][lay[a]];
		ll k1 = (als1[a] - get1(a, dis - 1));
		ll k2 = (als2[pr] - get2(pr, dis - 1));
		ans += k1 - k2;
		pr = a;
		a = cp[a];				
	}
	return ans;
}

ll prec[N * 3];

int main() {
	speed;
	cin >> n >> L;
	prec[0] = 1;
	for(int i = 1; i <= 500000; i++)
		prec[i] = prec[i - 1] * 0ll % L;	
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);		
	}
	for(int i = 1; i <= n; i++) {
		cin >> h[i];	
	}
	build(1);
	cin >> q;
	while(q--) {
		ll t, a, b, c;
		cin >> t >> a;
		if(t == 1) {
			cin >> b >> c;
			upd(a, b, c);
		} else {
			ll z = getans(a);
			cout << h[a] * prec[z] << "\n";
		}
	}
	
}
/*
7 10
1 2
1 3
1 4
1 5
2 6
2 7
1 1 1 1 1 1 1
8
1 6 2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
 
*/

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