oj.uz

Submission #588870

# Submission time Handle Problem Language Result Execution time Memory
588870 2022-07-04T06:42:37 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
30 / 100
 1463 ms 134360 KB 
#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] * 2ll % 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] % L << "\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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8916 KB Output is correct
2 Incorrect 7 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 12.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8916 KB Output is correct
2 Correct 1463 ms 127712 KB Output is correct
3 Correct 1336 ms 131352 KB Output is correct
4 Correct 1421 ms 133452 KB Output is correct
5 Correct 1099 ms 128424 KB Output is correct
6 Correct 1055 ms 128620 KB Output is correct
7 Correct 733 ms 128468 KB Output is correct
8 Correct 375 ms 128408 KB Output is correct
9 Correct 1249 ms 134360 KB Output is correct
10 Correct 1250 ms 132776 KB Output is correct
11 Correct 956 ms 129224 KB Output is correct
12 Correct 933 ms 127604 KB Output is correct
13 Correct 553 ms 128796 KB Output is correct
14 Correct 607 ms 129480 KB Output is correct
15 Correct 7 ms 8916 KB Output is correct
16 Correct 8 ms 9004 KB Output is correct
17 Correct 7 ms 8916 KB Output is correct
18 Correct 7 ms 8916 KB Output is correct
19 Correct 7 ms 8916 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8916 KB Output is correct
2 Incorrect 7 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -