oj.uz

Submission #589056

# Submission time Handle Problem Language Result Execution time Memory
589056 2022-07-04T09:04:40 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
21 / 100
 2864 ms 193532 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);
		}
	}
}
 
ll stp[N][42];
ll per[N][42];
 
 
void upd(ll a, ll c, ll b) {
	ll dis = 0;
	ll izn = a;
	int cnt = 0;
	const ll modu = L;
	ll kk = b;
	for(int j = c; j >= 0; j--) {
		stp[a][j] = stp[a][j] * kk % modu;
	}
	while(a) {
		if(cp[a] == 0)break;
		cnt++;
		dis = dist[izn][lay[cp[a]]];
		if(c - dis >= 0) {
			kk = b;
			for(int j = c - dis; j >= 0; j--) {
				stp[cp[a]][j] = stp[cp[a]][j] * kk % modu;
				per[a][j] = per[a][j] * kk % modu;
			}
		}				
		a = cp[a];
	}
}
 
ll phi = 0;
 
ll bp(ll a, ll b) {
	const ll z = L;
	ll c = 1ll;
	while(b) {
		if(b&1)
			c = c * a % z;
		b >>= 1ll;
		a = a * a % z;		
	}
	return c;
}
 
ll inv(ll a) {
	return bp(a, phi - 1);
}
 
ll getans(ll a) {
	ll dis = 0;
	ll izn = a;
	ll ans = stp[a][0];
	ll pr = a;
	const ll modu = L;
	a = cp[a];
	while(a) {
		dis = dist[izn][lay[a]];
		ll z = stp[a][min(41ll, dis)] * inv(per[pr][min(41ll, dis)]) % modu;
		ans = ans * z % modu;
		pr = a;
		a = cp[a];				
	}
	return ans;
}
 
ll prec[N * 3];
 
int main() {
	speed;
	cin >> n >> L;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= 41; j++)
			stp[i][j] = per[i][j] = 1;
	}
	prec[0] = 1;
	ll kek = L;
	ll ts = L;
	ll ans = L;
	for(int i = 2; i * i <= L; i++) {
		if(L % i == 0) {
			while(L % i == 0)L /= i;
			ans = ans - ans/i;
		}
	}
	if(L > 1)ans = ans - ans/L;
	phi = ans;
	L = ts;
	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 {
			cout << h[a] * getans(a) % kek << '\n';
		}
	}
	
}
/*
6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
6
1 5 1 7
1 4 1 9
1 5 0 7
1 1 1 3
1 6 1 4
2 4
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8916 KB Output is correct
2 Correct 7 ms 8972 KB Output is correct
3 Correct 6 ms 8916 KB Output is correct
4 Correct 10 ms 9812 KB Output is correct
5 Incorrect 10 ms 9788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8916 KB Output is correct
2 Correct 1994 ms 188416 KB Output is correct
3 Correct 891 ms 185412 KB Output is correct
4 Correct 1831 ms 192112 KB Output is correct
5 Correct 1423 ms 187004 KB Output is correct
6 Correct 1089 ms 186948 KB Output is correct
7 Correct 985 ms 187348 KB Output is correct
8 Correct 436 ms 187408 KB Output is correct
9 Correct 2615 ms 193392 KB Output is correct
10 Correct 1519 ms 190584 KB Output is correct
11 Correct 2323 ms 188360 KB Output is correct
12 Correct 1135 ms 185348 KB Output is correct
13 Correct 381 ms 185740 KB Output is correct
14 Correct 474 ms 185784 KB Output is correct
15 Correct 450 ms 185676 KB Output is correct
16 Correct 435 ms 185672 KB Output is correct
17 Correct 511 ms 186220 KB Output is correct
18 Correct 7 ms 9004 KB Output is correct
19 Correct 7 ms 8916 KB Output is correct
20 Correct 7 ms 8916 KB Output is correct
21 Correct 7 ms 8916 KB Output is correct
22 Correct 7 ms 8916 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8916 KB Output is correct
2 Correct 1994 ms 188416 KB Output is correct
3 Correct 891 ms 185412 KB Output is correct
4 Correct 1831 ms 192112 KB Output is correct
5 Correct 1423 ms 187004 KB Output is correct
6 Correct 1089 ms 186948 KB Output is correct
7 Correct 985 ms 187348 KB Output is correct
8 Correct 436 ms 187408 KB Output is correct
9 Correct 2615 ms 193392 KB Output is correct
10 Correct 1519 ms 190584 KB Output is correct
11 Correct 2323 ms 188360 KB Output is correct
12 Correct 1135 ms 185348 KB Output is correct
13 Correct 381 ms 185740 KB Output is correct
14 Correct 474 ms 185784 KB Output is correct
15 Correct 450 ms 185676 KB Output is correct
16 Correct 435 ms 185672 KB Output is correct
17 Correct 511 ms 186220 KB Output is correct
18 Correct 7 ms 9004 KB Output is correct
19 Correct 7 ms 8916 KB Output is correct
20 Correct 7 ms 8916 KB Output is correct
21 Correct 7 ms 8916 KB Output is correct
22 Correct 7 ms 8916 KB Output is correct
23 Correct 7 ms 8916 KB Output is correct
24 Incorrect 2104 ms 188628 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8916 KB Output is correct
2 Correct 2770 ms 190992 KB Output is correct
3 Correct 2276 ms 190084 KB Output is correct
4 Correct 2218 ms 190536 KB Output is correct
5 Correct 1818 ms 185140 KB Output is correct
6 Correct 1656 ms 185300 KB Output is correct
7 Correct 1436 ms 185504 KB Output is correct
8 Correct 499 ms 185588 KB Output is correct
9 Correct 2550 ms 190812 KB Output is correct
10 Correct 2288 ms 190080 KB Output is correct
11 Correct 2050 ms 185516 KB Output is correct
12 Correct 2148 ms 185032 KB Output is correct
13 Correct 1371 ms 185828 KB Output is correct
14 Correct 1391 ms 186596 KB Output is correct
15 Correct 7 ms 8916 KB Output is correct
16 Correct 10 ms 8916 KB Output is correct
17 Correct 7 ms 8916 KB Output is correct
18 Correct 8 ms 8916 KB Output is correct
19 Correct 7 ms 8916 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8916 KB Output is correct
2 Correct 7 ms 8972 KB Output is correct
3 Correct 6 ms 8916 KB Output is correct
4 Correct 10 ms 9812 KB Output is correct
5 Incorrect 10 ms 9788 KB Output isn't correct
6 Halted 0 ms 0 KB -