Submission #589085

#	Time	Username	Problem	Language	Result	Execution time	Memory
589085		Tekor	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	190 ms	399820 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'
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 2e5 + 100;
const int M = 4e5 + 100;
ll L;
ll binpow(ll a,ll b) {
	ll ans = 1,k = a;
	while(b) {
		if(b % 2)ans *= k;
		ans %= L;
		k *= k;
		k %= L;
		b /= 2ll;
	}
	return ans;
}
vector <int> g[N];
pii c[M];
ll a[N];
ll dop[N][42];
bool ban[N];
int pr[N],h[N],tin[N],tout[N],Tima,up[N][22],n,sz[N];
pii mxsz[N];
map <int,ll> canc[N][42];
void dfs_build1(int v,int p) {
	for(int i = 1;i <= 20;i++)up[v][i] = up[up[v][i - 1]][i - 1];
	tin[v] = ++Tima;
	for(auto to : g[v]) {
		if(to == p)continue;
		up[to][0] = v;
		h[to] = h[v] + 1;
		dfs_build1(to,v);
	}
	tout[v] = Tima;
}
bool upper(int v,int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int getD(int x,int y) {
	if(upper(x,y))return h[y] - h[x];
	if(upper(y,x))return h[x] - h[y];
	int val = h[x] + h[y];
	for(int i = 20;i >= 0;i--) {
		if(!upper(up[x][i],y)) {
			x = up[x][i];
		}
	}
	x = up[x][0];
	return val - 2 * h[x];
}
void dfs_rebuild(int v,int p) {
	sz[v] = 1;
	mxsz[v] = mp(-1,-1);
	for(auto to : g[v]) {
		if(to == p || ban[to])continue;
		dfs_rebuild(to,v);
		sz[v] += sz[to];
		mxsz[v] = max(mxsz[v],mp(sz[to],to));
	}
}
void dfs_build(int v,int p) {
	pr[v] = p;
	dfs_rebuild(v,-1);
	int bilo = sz[v];
	while(mxsz[v].f * 2 >= bilo) {
		v = mxsz[v].s;
	}
	ban[v] = 1;
	for(auto to : g[v]) {
		if(ban[to])continue;
		dfs_build(to,v);
	}
}
void upd(int x,int dist,ll w) {
	int v = x,bilo = -1;
	while(v != -1) {
		int dd = dist - getD(x,v);
		//cout << v << " " << bilo << " " << dd << en;
		if(dd >= 0) {
			dop[v][dd]++;
			if(bilo != -1)canc[v][dd][bilo]++;	
		}
		bilo = v;
		v = pr[v];
	}
}
ll get(int x) {
	int v = x;
	int bilo = -1;
	ll tek = 0;
	while(v != -1) {
		int dd = getD(x,v);
		for(int j = dd;j <= 40;j++)  {
			tek += dop[v][j];
			if(bilo != -1)tek -= canc[v][j][bilo];
		}
		bilo = v;
		v = pr[v];
	}
	return (binpow(2ll,tek) * a[x]) % L;
}
/*

*/
void solve() {
	cin >> n >> L;
	for(int i = 1;i <= n;i++) {
		pr[i] = -1;
		for(int j = 0;j <= 40;j++)dop[i][j] = 0;
	}
	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];
	int q;
	cin >> q;
	dfs_build1(1,-1);
	dfs_build(1,-1);
	//cout << "OK" << endl;
	for(int i = 1;i <= q;i++) {
		int typ;
		cin >> typ;
		if(typ == 1) {
			int x,dist;
			ll w;
			cin >> x >> dist >> w;
			upd(x,dist,w);
		}else {
			int x;
			cin >> x;
			cout << get(x) << en;
		}
	}
}

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

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