oj.uz

Submission #589095

# Submission time Handle Problem Language Result Execution time Memory
589095 2022-07-04T09:19:06 Z Tekor Sprinkler (JOI22_sprinkler) C++17
0 / 100
 3654 ms 978748 KB 
#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));
	}
}
int dfs_build(int v,int 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;
		pr[dfs_build(to,v)] = v;
	}
	return 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.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 399680 KB Output is correct
2 Incorrect 172 ms 399800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 399716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 399716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 399704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 399804 KB Output is correct
2 Correct 3654 ms 978748 KB Output is correct
3 Correct 2145 ms 729152 KB Output is correct
4 Correct 3010 ms 927908 KB Output is correct
5 Incorrect 2959 ms 884108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 399680 KB Output is correct
2 Incorrect 172 ms 399800 KB Output isn't correct
3 Halted 0 ms 0 KB -