oj.uz

Submission #571951

# Submission time Handle Problem Language Result Execution time Memory
571951 2022-06-03T08:03:55 Z 8e7 Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 42712 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 4
#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[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 ret = h[n];
	while (cur < maxd && n) {
		if (b[n].query(cur)) {
			ret = 0;
			break;
		}
		prv = pi[n];
		n = par[n];
		cur++;
	}
	return ret;	
}
int main() {
	io
	int n;
	cin >> n >> 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 Execution timed out 4054 ms 11220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Execution timed out 4072 ms 42712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 11220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 11220 KB Time limit exceeded
2 Halted 0 ms 0 KB -