oj.uz

Submission #589032

# Submission time Handle Problem Language Result Execution time Memory
589032 2022-07-04T08:55:58 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
21 / 100
 2847 ms 201508 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 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) % L << '\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 6 ms 8916 KB Output is correct
4 Correct 9 ms 9900 KB Output is correct
5 Incorrect 10 ms 9900 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 7 ms 8916 KB Output is correct
2 Correct 1964 ms 188244 KB Output is correct
3 Correct 921 ms 193452 KB Output is correct
4 Correct 1771 ms 200440 KB Output is correct
5 Correct 1399 ms 195396 KB Output is correct
6 Correct 1012 ms 195616 KB Output is correct
7 Correct 1010 ms 195680 KB Output is correct
8 Correct 421 ms 195688 KB Output is correct
9 Correct 2376 ms 201508 KB Output is correct
10 Correct 1168 ms 198724 KB Output is correct
11 Correct 1916 ms 196496 KB Output is correct
12 Correct 879 ms 193552 KB Output is correct
13 Correct 334 ms 193964 KB Output is correct
14 Correct 343 ms 193988 KB Output is correct
15 Correct 394 ms 193964 KB Output is correct
16 Correct 433 ms 193840 KB Output is correct
17 Correct 463 ms 194196 KB Output is correct
18 Correct 7 ms 9044 KB Output is correct
19 Correct 8 ms 8916 KB Output is correct
20 Correct 7 ms 9000 KB Output is correct
21 Correct 7 ms 9004 KB Output is correct
22 Correct 7 ms 9000 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8916 KB Output is correct
2 Correct 1964 ms 188244 KB Output is correct
3 Correct 921 ms 193452 KB Output is correct
4 Correct 1771 ms 200440 KB Output is correct
5 Correct 1399 ms 195396 KB Output is correct
6 Correct 1012 ms 195616 KB Output is correct
7 Correct 1010 ms 195680 KB Output is correct
8 Correct 421 ms 195688 KB Output is correct
9 Correct 2376 ms 201508 KB Output is correct
10 Correct 1168 ms 198724 KB Output is correct
11 Correct 1916 ms 196496 KB Output is correct
12 Correct 879 ms 193552 KB Output is correct
13 Correct 334 ms 193964 KB Output is correct
14 Correct 343 ms 193988 KB Output is correct
15 Correct 394 ms 193964 KB Output is correct
16 Correct 433 ms 193840 KB Output is correct
17 Correct 463 ms 194196 KB Output is correct
18 Correct 7 ms 9044 KB Output is correct
19 Correct 8 ms 8916 KB Output is correct
20 Correct 7 ms 9000 KB Output is correct
21 Correct 7 ms 9004 KB Output is correct
22 Correct 7 ms 9000 KB Output is correct
23 Correct 7 ms 8916 KB Output is correct
24 Incorrect 1957 ms 194668 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 6 ms 8916 KB Output is correct
2 Correct 2671 ms 190864 KB Output is correct
3 Correct 2243 ms 196100 KB Output is correct
4 Correct 2080 ms 194764 KB Output is correct
5 Correct 1731 ms 189704 KB Output is correct
6 Correct 1410 ms 189880 KB Output is correct
7 Correct 1263 ms 190000 KB Output is correct
8 Correct 481 ms 190060 KB Output is correct
9 Correct 2577 ms 195288 KB Output is correct
10 Correct 2286 ms 194616 KB Output is correct
11 Correct 2009 ms 190008 KB Output is correct
12 Correct 2052 ms 189184 KB Output is correct
13 Correct 1353 ms 190176 KB Output is correct
14 Correct 1433 ms 190752 KB Output is correct
15 Correct 7 ms 8900 KB Output is correct
16 Correct 8 ms 8916 KB Output is correct
17 Correct 9 ms 8916 KB Output is correct
18 Correct 8 ms 8932 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 8 ms 8916 KB Output is correct
2 Incorrect 2847 ms 193464 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 6 ms 8916 KB Output is correct
4 Correct 9 ms 9900 KB Output is correct
5 Incorrect 10 ms 9900 KB Output isn't correct
6 Halted 0 ms 0 KB -