oj.uz

Submission #589273

# Submission time Handle Problem Language Result Execution time Memory
589273 2022-07-04T11:32:16 Z LastRonin Sprinkler (JOI22_sprinkler) C++14
0 / 100
 369 ms 116416 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 + 60;
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, gl[N];
vector<int> g[N];
int dp[N];
int p[N], h[N];
int pr[N][41];

int mul(ll a, ll b) {	
	const ll z = L;
	return a * b % z;
}

void dfs(ll v, ll pr) {
	p[v] = pr;
	for(auto u : g[v]) {
		if(u == pr)continue;
		dfs(u, v);
	}

}

ll ans[N];

ll t[N], A[N], b[N], c[N];
 
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];	
	}
	dfs(1, 0);
	p[1] = n + 1;
	for(int j = 1; j <= 40; j++) {
		p[n + j] = n + j + 1;		
	}
	for(int j = 1; j <= n; j++) {
		pr[j][0] = j;
		for(int i = 1; i <= 40; i++) {
			pr[j][i] = p[pr[j][i - 1]];
		}
	}
	cin >> q;
	for(int i = 1; i <= q; i++) {
		cin >> t[i] >> A[i];
		if(t[i] == 1)cin >> b[i] >> c[i];
		else ans[i] = 1;
	}
	for(int B = 40; B >= 0; B--) {
		for(int i = 1; i <= n + 40; i++) {
			dp[i] = 1;
		}
		for(int i = 1; i <= q; i++) {
			if(t[i] == 1 && b[i] != B)continue;
			int a = A[i];			
			if(t[i] == 1) {
				dp[a] = mul(dp[a], c[i]);
				b[i]--;
				A[i] = p[A[i]];
			} else {
				
				if(B != 0)
					ans[i] = mul(ans[i], dp[pr[a][B - 1]]);
				ans[i] = mul(ans[i], dp[pr[a][B]]);					
			}
		}
	}
	for(int i = 1; i <= q; i++) {
		if(t[i] == 2)cout << ans[i] << "\n";
	}
}
/*
4 7
1 2
2 3
3 4
1 1 1 1
6
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Incorrect 4 ms 5076 KB Output isn't correct
3 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
0 / 12.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Runtime error 369 ms 116416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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