oj.uz

Submission #589046

# Submission time Handle Problem Language Result Execution time Memory
589046 2022-07-04T09:01:22 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
12 / 100
 3350 ms 191456 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;
		//kk = kk * b % 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;
				//kk = kk * b % modu; 
			}
			//add1(cp[a], c - dis, b);
			//add2(a, c - dis, b);
		}				
		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;
	L *= 5ll;
	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 7 ms 8916 KB Output is correct
2 Correct 7 ms 8916 KB Output is correct
3 Correct 7 ms 8916 KB Output is correct
4 Correct 10 ms 9812 KB Output is correct
5 Incorrect 10 ms 9896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8916 KB Output is correct
2 Incorrect 1994 ms 188652 KB Output isn't correct
3 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 2858 ms 191152 KB Output is correct
3 Correct 2240 ms 190268 KB Output is correct
4 Correct 2190 ms 190748 KB Output is correct
5 Correct 1740 ms 185540 KB Output is correct
6 Correct 1543 ms 185560 KB Output is correct
7 Correct 1476 ms 185732 KB Output is correct
8 Correct 549 ms 185804 KB Output is correct
9 Correct 3350 ms 191048 KB Output is correct
10 Correct 2461 ms 190152 KB Output is correct
11 Correct 2293 ms 185660 KB Output is correct
12 Correct 2294 ms 185096 KB Output is correct
13 Correct 1547 ms 185972 KB Output is correct
14 Correct 1555 ms 186824 KB Output is correct
15 Correct 8 ms 8892 KB Output is correct
16 Correct 8 ms 8916 KB Output is correct
17 Correct 9 ms 9012 KB Output is correct
18 Correct 9 ms 8916 KB Output is correct
19 Correct 8 ms 8916 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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