oj.uz

Submission #588860

# Submission time Handle Problem Language Result Execution time Memory
588860 2022-07-04T06:39:27 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
12 / 100
 1267 ms 128472 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;
}

int main() {
	speed;
	cin >> n >> 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);
			if(z > 0)cout << 0 << "\n";
			else cout << h[a] << "\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 Incorrect 4 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5080 KB Output is correct
2 Correct 1210 ms 121332 KB Output is correct
3 Correct 1186 ms 127192 KB Output is correct
4 Correct 1209 ms 128024 KB Output is correct
5 Correct 879 ms 123176 KB Output is correct
6 Correct 725 ms 123144 KB Output is correct
7 Correct 714 ms 123356 KB Output is correct
8 Correct 364 ms 123644 KB Output is correct
9 Correct 1190 ms 127940 KB Output is correct
10 Correct 1267 ms 128472 KB Output is correct
11 Correct 862 ms 122628 KB Output is correct
12 Correct 921 ms 123396 KB Output is correct
13 Correct 619 ms 124412 KB Output is correct
14 Correct 596 ms 125128 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 4 ms 5032 KB Output is correct
17 Correct 5 ms 4980 KB Output is correct
18 Correct 4 ms 5036 KB Output is correct
19 Correct 5 ms 5076 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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