oj.uz

Submission #571979

# Submission time Handle Problem Language Result Execution time Memory
571979 2022-06-03T08:16:24 Z 8e7 Sprinkler (JOI22_sprinkler) C++17
30 / 100
 2037 ms 115744 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxd 42
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int mod;
struct BIT{
	vector<ll> bit;
	int n;
	void init(int _n) {
		n = _n;
		bit.resize(maxd);
		for (int i = 0;i < maxd;i++) bit[i] = 0;
	}
	void modify(int d, int val) {
		d = maxd - 1 - d;
		for (;d < maxd;d += d & (-d)) {
			bit[d] += val;
		}
	}	
	ll query(int d) {
		d = maxd - 1 - d;
		ll ret = 0;
		for (;d > 0;d -= d & (-d)) ret += bit[d];
		return ret;
	}
} b[maxn];
vector<int> adj[maxn];
int par[maxn], pi[maxn], leaf[maxn];
void dfs(int n, int pa) {
	par[n] = pa;
	leaf[n] = 1;
	for (int v:adj[n]) {
		if (v != pa) {
			dfs(v, n);
			pi[v] = leaf[n]++;
		}
	}
	b[n].init(maxd);
	//debug(n, leaf[n]);
}
ll h[maxn], po[2 * maxn];
void modify(int n, int d, int w) {
	int prv = 0;
	while (d >= 0 && n) {
		b[n].modify(d, w); 
		prv = pi[n];
		n = par[n];
		d--;
	}
}
ll query(int n) {
	int cur = 0, prv = -1;
	ll tmp = h[n];
	ll ret = 0;
	while (cur < maxd && n) {
		ret += b[n].query(cur);
		if (par[n]) ret -= b[n].query(cur+2);
		prv = pi[n];
		n = par[n];
		cur++;
	}
	return tmp * po[ret] % mod;	
}
int main() {
	io
	int n;
	cin >> n >> mod;
	po[0] = 1;
	for (int i = 1;i < 2 * maxn;i++) po[i] = po[i-1] * 2 % mod;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) cin >> h[i]; 
	dfs(1, 0);
	int q;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			modify(x, d, 1);
		} else {
			int x;
			cin >> x;
			cout << query(x) << "\n";
		}
	}
}

Compilation message

sprinkler.cpp: In function 'void modify(int, int, int)':
sprinkler.cpp:60:6: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
   60 |  int prv = 0;
      |      ^~~
sprinkler.cpp: In function 'long long int query(int)':
sprinkler.cpp:69:15: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
   69 |  int cur = 0, prv = -1;
      |               ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Incorrect 9 ms 14360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14356 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 12 ms 14420 KB Output is correct
2 Correct 1360 ms 105760 KB Output is correct
3 Correct 2025 ms 109324 KB Output is correct
4 Correct 1313 ms 111264 KB Output is correct
5 Correct 1094 ms 103832 KB Output is correct
6 Correct 647 ms 103608 KB Output is correct
7 Correct 567 ms 103888 KB Output is correct
8 Correct 401 ms 104280 KB Output is correct
9 Correct 1341 ms 115744 KB Output is correct
10 Correct 2037 ms 114368 KB Output is correct
11 Correct 969 ms 104492 KB Output is correct
12 Correct 1495 ms 103040 KB Output is correct
13 Correct 814 ms 103888 KB Output is correct
14 Correct 881 ms 104428 KB Output is correct
15 Correct 11 ms 14420 KB Output is correct
16 Correct 11 ms 14420 KB Output is correct
17 Correct 10 ms 14420 KB Output is correct
18 Correct 10 ms 14364 KB Output is correct
19 Correct 9 ms 14364 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Incorrect 9 ms 14360 KB Output isn't correct
3 Halted 0 ms 0 KB -