oj.uz

Submission #589026

# Submission time Handle Problem Language Result Execution time Memory
589026 2022-07-04T08:54:25 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
30 / 100
 1682 ms 132188 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][42];
int per[N][42];
 
void upd(ll a, ll c, ll b) {
	ll dis = 0;
	ll izn = a;
	int cnt = 0;
	for(int j = c; j >= 0; j--) {
		stp[a][j]++;
	}
	while(a) {
		if(cp[a] == 0)break;
		cnt++;
		assert(cnt <= 40);
		dis = dist[izn][lay[cp[a]]];
		if(c - dis >= 0) {
			for(int j = c - dis; j >= 0; j--) {
				stp[cp[a]][j]++;
				per[a][j]++;			 	
			}
		}				
		a = cp[a];
	}
}
 
ll getans(ll a) {
	ll dis = 0;
	ll izn = a;
	ll ans = stp[a][0];
	ll pr = a;
	a = cp[a];
	while(a) {
		dis = dist[izn][lay[a]];
		ans = ans + stp[a][min(41ll, dis)] - per[pr][min(41ll, dis)];
		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 7 ms 8916 KB Output is correct
2 Incorrect 8 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 8916 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 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8976 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 7 ms 8972 KB Output is correct
2 Correct 1216 ms 127648 KB Output is correct
3 Correct 1540 ms 130532 KB Output is correct
4 Correct 1340 ms 130492 KB Output is correct
5 Correct 970 ms 125456 KB Output is correct
6 Correct 870 ms 125536 KB Output is correct
7 Correct 726 ms 125704 KB Output is correct
8 Correct 415 ms 125752 KB Output is correct
9 Correct 1356 ms 132188 KB Output is correct
10 Correct 1682 ms 128916 KB Output is correct
11 Correct 1020 ms 126956 KB Output is correct
12 Correct 1120 ms 123712 KB Output is correct
13 Correct 746 ms 124184 KB Output is correct
14 Correct 799 ms 124928 KB Output is correct
15 Correct 7 ms 8916 KB Output is correct
16 Correct 7 ms 8916 KB Output is correct
17 Correct 8 ms 8916 KB Output is correct
18 Correct 7 ms 9012 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 7 ms 8916 KB Output is correct
2 Incorrect 8 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -