oj.uz

Submission #97754

# Submission time Handle Problem Language Result Execution time Memory
97754 2019-02-18T10:20:03 Z jhnah917 None (KOI16_tree) C++14
100 / 100
 609 ms 36576 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

template <typename T>
class SegTree{
	private:
		T tree[808080];
		int lim;
		function<T(const T a, const T b)> f;
	public:
		void init(int n, function<T(const T a, const T b)> func){
			f = func;
			for(lim = 1; lim <= n; lim <<= 1);
		}
		void update(int x, T v){
			x += lim;
			tree[x] = v;
			while(x > 1){
				x >>= 1;
				tree[x] = f(tree[2*x], tree[2*x+1]);
			}
		}
		T query(int s, int e){
			s += lim;
			e += lim;
			T ret = 1;
			while(s < e){
				if(s%2 == 1) ret = f(ret, tree[s++]);
				if(e%2 == 0) ret = f(ret, tree[e--]);
				s >>= 1;
				e >>= 1;
			}
			if(s == e) ret = f(ret, tree[s]);
			return ret;
		}
};

template <typename T>
class HLD{
	private:
		int dn;
		int par[202020], size[202020], depth[202020], lab[202020];
		int id[202020], top[202020];
		SegTree<T> tree;
		function<T(const T a, const T b)> f;
		
		int dfs(int now, int prv){
			par[now] = prv; size[now] = 1;
			for(auto &t: g[now]){
				int nxt = t.first;
				if(nxt != prv){
					depth[nxt] = depth[now] + 1;
					size[now] += dfs(nxt, now);
				}
			}
			return size[now];
		}
		void decom(int now, int prv, int chain){
			lab[now] = dn;
			id[dn] = chain;
			top[chain] = dn++;
			int heavy = -1;
			for(auto &t: g[now]){
				int nxt = t.first;
				if(nxt != prv && (heavy == -1 || size[nxt] > size[heavy])) heavy = nxt;
			}
			if(heavy != -1) decom(heavy, now, chain);
			for(auto &t: g[now]){
				int nxt = t.first;
				if(nxt != prv && nxt != heavy) decom(nxt, now, nxt);
			}
		}
		
	public:
		vector<p> g[202020];
	
		void init(int root, function<T(const T a, const T b)> func){
			//init value
			f = func;
	    	dn = 0;
	    	memset(id,-1,sizeof(id));
			memset(top,-1,sizeof(top));
			
			//pre-processing
	    	dfs(root,-1);
			decom(root,-1,root);
			
			//set edge's weight
			vector<T> a(202020);
			for(int i=0;i<202020;i++){
				for(auto &t: g[i]){
					int next = t.first, w = t.second;
					int v = lab[next];
					if(depth[i] < depth[next]) a[v] = w;
				}
			}
			tree.init(a.size(), f);
			for(int i=0; i<a.size(); i++) tree.update(i, a[i]);
		}
	
		void update(int u, int v, T k){
			if(depth[u] < depth[v]) swap(u, v);
			tree.update(lab[u], k);
		}
	
		T query(int u, int v){
			T ret = 1;
			u = lab[u], v = lab[v];
			while(id[u] != id[v]){
				int uHead = id[u], vHead = id[v];
				if(depth[uHead] > depth[vHead]){
					ret = f(ret, tree.query(lab[uHead], u));
					u = lab[par[uHead]];
				}
				else{
					ret = f(ret,tree.query(lab[vHead], v));
					v = lab[par[vHead]];
				}
			}
			ret = f(ret, tree.query(min(u, v)+1, max(u,v)));
			return ret;
		}
};

HLD<int> hld;
vector<int> par(202020);

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i=2; i<=n; i++){
		int t; cin >> t;
		par[i] = t;
		hld.g[t].push_back({i, 1});
	}
	hld.init(1, [](int a, int b){
		return a && b;
	});
	
	while(q--){
		int a, b, op; cin >> a >> b >> op;
		int res = hld.query(a, b);
		if(res) cout << "YES\n";
		else cout << "NO\n";
		if(op == 1){
			if(res) hld.update(a, par[a], 0);
			else hld.update(b, par[b], 0);
		}
	}
}

Compilation message

tree.cpp: In instantiation of 'void HLD<T>::init(int, std::function<T(T, T)>) [with T = int]':
tree.cpp:140:3:   required from here
tree.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<a.size(); i++) tree.update(i, a[i]);

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9956 KB Output is correct
2 Correct 31 ms 9980 KB Output is correct
3 Correct 31 ms 9948 KB Output is correct
4 Correct 29 ms 9976 KB Output is correct
5 Correct 29 ms 9976 KB Output is correct
6 Correct 28 ms 9976 KB Output is correct
7 Correct 24 ms 9984 KB Output is correct
8 Correct 30 ms 9996 KB Output is correct
9 Correct 29 ms 9976 KB Output is correct
10 Correct 37 ms 10008 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9956 KB Output is correct
2 Correct 31 ms 9980 KB Output is correct
3 Correct 31 ms 9948 KB Output is correct
4 Correct 29 ms 9976 KB Output is correct
5 Correct 29 ms 9976 KB Output is correct
6 Correct 28 ms 9976 KB Output is correct
7 Correct 24 ms 9984 KB Output is correct
8 Correct 30 ms 9996 KB Output is correct
9 Correct 29 ms 9976 KB Output is correct
10 Correct 37 ms 10008 KB Output is correct
11 Correct 34 ms 9976 KB Output is correct
12 Correct 37 ms 9976 KB Output is correct
13 Correct 35 ms 9980 KB Output is correct
14 Correct 30 ms 9976 KB Output is correct
15 Correct 33 ms 9956 KB Output is correct
16 Correct 31 ms 9984 KB Output is correct
17 Correct 10 ms 9904 KB Output is correct
18 Correct 37 ms 9976 KB Output is correct
19 Correct 29 ms 9988 KB Output is correct
20 Correct 33 ms 9976 KB Output is correct
21 Correct 30 ms 9976 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9956 KB Output is correct
2 Correct 31 ms 9980 KB Output is correct
3 Correct 31 ms 9948 KB Output is correct
4 Correct 29 ms 9976 KB Output is correct
5 Correct 29 ms 9976 KB Output is correct
6 Correct 28 ms 9976 KB Output is correct
7 Correct 24 ms 9984 KB Output is correct
8 Correct 30 ms 9996 KB Output is correct
9 Correct 29 ms 9976 KB Output is correct
10 Correct 37 ms 10008 KB Output is correct
11 Correct 34 ms 9976 KB Output is correct
12 Correct 37 ms 9976 KB Output is correct
13 Correct 35 ms 9980 KB Output is correct
14 Correct 30 ms 9976 KB Output is correct
15 Correct 33 ms 9956 KB Output is correct
16 Correct 31 ms 9984 KB Output is correct
17 Correct 10 ms 9904 KB Output is correct
18 Correct 37 ms 9976 KB Output is correct
19 Correct 29 ms 9988 KB Output is correct
20 Correct 33 ms 9976 KB Output is correct
21 Correct 30 ms 9976 KB Output is correct
22 Correct 171 ms 12000 KB Output is correct
23 Correct 179 ms 12048 KB Output is correct
24 Correct 137 ms 12132 KB Output is correct
25 Correct 154 ms 11996 KB Output is correct
26 Correct 163 ms 12096 KB Output is correct
27 Correct 138 ms 12072 KB Output is correct
28 Correct 157 ms 12248 KB Output is correct
29 Correct 130 ms 12052 KB Output is correct
30 Correct 129 ms 12340 KB Output is correct
31 Correct 143 ms 12128 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9956 KB Output is correct
2 Correct 31 ms 9980 KB Output is correct
3 Correct 31 ms 9948 KB Output is correct
4 Correct 29 ms 9976 KB Output is correct
5 Correct 29 ms 9976 KB Output is correct
6 Correct 28 ms 9976 KB Output is correct
7 Correct 24 ms 9984 KB Output is correct
8 Correct 30 ms 9996 KB Output is correct
9 Correct 29 ms 9976 KB Output is correct
10 Correct 37 ms 10008 KB Output is correct
11 Correct 494 ms 35944 KB Output is correct
12 Correct 466 ms 35948 KB Output is correct
13 Correct 473 ms 35952 KB Output is correct
14 Correct 497 ms 35868 KB Output is correct
15 Correct 454 ms 35804 KB Output is correct
16 Correct 474 ms 35936 KB Output is correct
17 Correct 407 ms 36576 KB Output is correct
18 Correct 432 ms 36424 KB Output is correct
19 Correct 420 ms 36448 KB Output is correct
20 Correct 412 ms 36444 KB Output is correct
21 Correct 483 ms 36036 KB Output is correct

Subtask #5
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9956 KB Output is correct
2 Correct 31 ms 9980 KB Output is correct
3 Correct 31 ms 9948 KB Output is correct
4 Correct 29 ms 9976 KB Output is correct
5 Correct 29 ms 9976 KB Output is correct
6 Correct 28 ms 9976 KB Output is correct
7 Correct 24 ms 9984 KB Output is correct
8 Correct 30 ms 9996 KB Output is correct
9 Correct 29 ms 9976 KB Output is correct
10 Correct 37 ms 10008 KB Output is correct
11 Correct 34 ms 9976 KB Output is correct
12 Correct 37 ms 9976 KB Output is correct
13 Correct 35 ms 9980 KB Output is correct
14 Correct 30 ms 9976 KB Output is correct
15 Correct 33 ms 9956 KB Output is correct
16 Correct 31 ms 9984 KB Output is correct
17 Correct 10 ms 9904 KB Output is correct
18 Correct 37 ms 9976 KB Output is correct
19 Correct 29 ms 9988 KB Output is correct
20 Correct 33 ms 9976 KB Output is correct
21 Correct 30 ms 9976 KB Output is correct
22 Correct 171 ms 12000 KB Output is correct
23 Correct 179 ms 12048 KB Output is correct
24 Correct 137 ms 12132 KB Output is correct
25 Correct 154 ms 11996 KB Output is correct
26 Correct 163 ms 12096 KB Output is correct
27 Correct 138 ms 12072 KB Output is correct
28 Correct 157 ms 12248 KB Output is correct
29 Correct 130 ms 12052 KB Output is correct
30 Correct 129 ms 12340 KB Output is correct
31 Correct 143 ms 12128 KB Output is correct
32 Correct 494 ms 35944 KB Output is correct
33 Correct 466 ms 35948 KB Output is correct
34 Correct 473 ms 35952 KB Output is correct
35 Correct 497 ms 35868 KB Output is correct
36 Correct 454 ms 35804 KB Output is correct
37 Correct 474 ms 35936 KB Output is correct
38 Correct 407 ms 36576 KB Output is correct
39 Correct 432 ms 36424 KB Output is correct
40 Correct 420 ms 36448 KB Output is correct
41 Correct 412 ms 36444 KB Output is correct
42 Correct 483 ms 36036 KB Output is correct
43 Correct 609 ms 19940 KB Output is correct
44 Correct 530 ms 19676 KB Output is correct
45 Correct 531 ms 19628 KB Output is correct
46 Correct 507 ms 19696 KB Output is correct
47 Correct 487 ms 19644 KB Output is correct
48 Correct 176 ms 19196 KB Output is correct
49 Correct 161 ms 19144 KB Output is correct
50 Correct 224 ms 19088 KB Output is correct
51 Correct 447 ms 26720 KB Output is correct