oj.uz

답안 #571957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571957 2022-06-03T08:05:30 Z 8e7 Sprinkler (JOI22_sprinkler) C++17
12 / 100
 1996 ms 110224 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[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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 680 ms 103656 KB Output is correct
3 Correct 1902 ms 108616 KB Output is correct
4 Correct 888 ms 108404 KB Output is correct
5 Correct 735 ms 98980 KB Output is correct
6 Correct 523 ms 99076 KB Output is correct
7 Correct 508 ms 99148 KB Output is correct
8 Correct 449 ms 99704 KB Output is correct
9 Correct 697 ms 107552 KB Output is correct
10 Correct 1996 ms 110224 KB Output is correct
11 Correct 705 ms 98716 KB Output is correct
12 Correct 1624 ms 99444 KB Output is correct
13 Correct 904 ms 100388 KB Output is correct
14 Correct 827 ms 100948 KB Output is correct
15 Correct 7 ms 11220 KB Output is correct
16 Correct 7 ms 11244 KB Output is correct
17 Correct 7 ms 11220 KB Output is correct
18 Correct 6 ms 11220 KB Output is correct
19 Correct 6 ms 11220 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -