Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
8	-is-this-fft-	148
9	pajenegod	145
10	BledDest	144

Hi all!

Recently, I tried to implement a HLD struct. However, my local computer shows Segmentation Fault verdict as soon as I set the constraint of N to 1e5, the online judge shows TLE verdict btw. Small constraint on N works just fine. Here is the code:

Segmentation Fault Code

#include<bits/stdc++.h>

using namespace std;

#define nl '\n'

const int N = 1e5 + 5; 

int n;
template<typename seg_t>
struct HLD{
	int P[N][20];
	int parent[N];
	int depth[N];
	int child[N];
	int bigChild[N];
	int chain[N];
	seg_t arr[N];
	seg_t tree[3 * N];
	int label[N];
	int label_time = 0;
	vector<int> g[N];

	void update(int u, int low, int high, int idx, int val){
		if(low > idx || high < idx) return;
		if(low == high){
			tree[u] = val;
			return;
		}
		int mid = (low + high) / 2;
		update(2 * u, low, mid, idx, val);
		update(2 * u + 1, mid + 1, high, idx, val);
		tree[u] = tree[2 * u] ^ tree[2 * u + 1];
	}
	seg_t get(int u, int low, int high, int l, int r){
		if(low > r || high < l) return 0;
		if(low >= l && high <= r) return tree[u];
		int mid = (low + high) / 2;
		return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
	}
	void init(int root){
		for(int i = 0; i < 3 * N; i++)
			tree[i] = 0;
		for(int i = 1; i < n; i++){
			int u, v;
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		for(int i = 0; i <= n; i++){
			parent[i] = -1;
			chain[i] = i;
		}
		parent[root] = root;
		dfs(root, 0);
		buildLCA();
		dfs_labels(arr, 1, -1);
	}
	void dfs(int u, int level){
		depth[u] = level;
		child[u] = 1;
		int bigc = -1, bigv = -1;

		for(auto x: g[u]){
			if(parent[x] == -1){
				parent[x] = u;
				dfs(x, level + 1);
				child[u] += child[x];
				if(child[x] > bigv){
					bigc = x;
					bigv = child[x];
				}
			}
		}
		bigChild[u] = bigc;
	}
	void buildLCA(){
		for(int i = 0; i <= n; i++){
			for(int j = 1; j <= trunc(log2(n)); j++)
				P[i][j] = -1;
		}
		for(int i = 1; i <= n; i++)
			P[i][0] = parent[i];
		for(int j = 1; j <= trunc(log2(n)); j++)
			for(int i = 0; i <= n; i++)
				if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];
	}
	int lca(int u, int v){
		if(depth[u] < depth[v]) swap(u, v);
		int x = 1;
		while(x <= log2(depth[u])) x++;
		x--;
		for(int i = x; i >= 0; i--)
			if(depth[u] - (1<<i) >= depth[v]) u = P[u][i];
		if(u == v) return u;
		for(int i = x; i >= 0; i--)
			if(P[u][i] != -1 && P[u][i] != P[v][i])
				u = P[u][i], v = P[v][i];
		return parent[u];
	}
	int k_th_ancestor(int u, int k){
		if(k == 0) return u;
		int cur = u;
		for(int i = 17; i >= 0; i--){
			if(k >= pow(2, i)){
				k -= pow(2, i);
				cur = P[cur][i];
			}
		}
		return cur;
	}
	void dfs_labels(seg_t* a, int u, int v){
		label[u] = label_time++;
		update(1, 0, n - 1, label[u], a[u]);
		if(bigChild[u] != -1) dfs_labels(a, bigChild[u], u);
		for(auto x: g[u]){
			if(x != v && x != bigChild[u])
				dfs_labels(a, x, u);
		}
	}
	void dfs_chains(int u, int v){
		if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
		for(auto x: g[u]){
			if(x == v) continue;
			dfs_chains(x, u);
		}
	}
	seg_t query_chain(int u, int p){
		seg_t res = 0;
		while(depth[p] < depth[u]){
			int top = chain[u];
			if(depth[top] <= depth[p]){
				int diff = depth[u] - depth[p];
				top = k_th_ancestor(u, diff - 1);
			}
			res = res ^ get(1, 0, n - 1, label[top], label[u]);
			u = parent[top];
		}
		return res;
	}
	seg_t query(int u, int v){
		int anc = lca(u, v);
		seg_t res = query_chain(u, anc) ^ query_chain(v, anc);
		res ^= get(1, 0, n - 1, label[anc], label[anc]);
		return res;
	}
};
void Solve(){
	int q;
	cin>>n>>q;
	HLD<int> h;
	for(int i = 1; i <= n; i++)
		cin>>h.arr[i];
	h.init(1);
	while(q--){
		int t, x, y;
		cin>>t>>x>>y;
		if(t == 1) h.update(1, 0, n - 1, h.label[x], y);
		else cout<<h.query(x, y)<<nl;
	}

}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	Solve();
}

So, I tried to rewrite the same code without using struct. This time my local computer ran smoothly and the online judge showed AC verdict.

The AC code:

#include<bits/stdc++.h>

using namespace std;

#define nl '\n'

const int N = 1e5 + 5;
int n;

vector<int> g[N];
int arr[N];
int bigChild[N];
int child[N];
int depth[N];
int chain[N];
int label[N], label_time;
int parent[N];
int lca_lift[N][20];

int tree[3 * N];

int k_th_ancestor(int u, int k);
void lca_dfs(int u, int p);
void dfs_size(int u, int p, int level);
void dfs_chains(int u, int p);
void dfs_labels(int u, int p);

void update(int u, int low, int high, int idx, int val){
	if(low > idx || high < idx) return;
	if(low == high){
		tree[u] = val;
		return;
	}
	int mid = (low + high) / 2;
	update(2 * u, low, mid, idx, val);
	update(2 * u + 1, mid + 1, high, idx, val);
	tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
int get(int u, int low, int high, int l, int r){
	if(low > r || high < l) return 0;
	if(low >= l && high <= r) return tree[u];
	int mid = (low + high) / 2;
	return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
} 
void init_arrays(){
	for(int i = 0; i < N; i++)
		chain[i] = i;
	for(int i = 0; i < 3 * N; i++)
		tree[i] = 0;
}
void addEdge(int u, int v){
	g[u].push_back(v);
	g[v].push_back(u);
}
void initTree(int root){
	lca_dfs(root, -1);
	dfs_size(root, -1, 0);
	dfs_chains(root, -1);
	label_time = 0;
	dfs_labels(root, -1);
}
void lca_dfs(int u, int p){
	lca_lift[u][0] = p;
	for(int i = 1; i < 20; i++){
		if(lca_lift[u][i - 1] == -1) lca_lift[u][i] = -1;
		else lca_lift[u][i] = lca_lift[lca_lift[u][i - 1]][i - 1];
	}
	for(auto x: g[u])
		if(x != p) lca_dfs(x, u);
}
void dfs_size(int u, int p, int level){
	child[u] = 1;
	depth[u] = level;
	parent[u] = p;
	int bigc = -1, bigv = -1;
	for(auto x: g[u]){
		if(x == p) continue;
		dfs_size(x, u, level + 1);
		child[u] += child[x];
		if(child[x] > bigv){
			bigv = child[x];
			bigc = x;
		}
	}
	bigChild[u] = bigc;
}
void dfs_chains(int u, int p){
	if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
	for(auto x: g[u]){
		if(x == p) continue;
		dfs_chains(x, u);
	}
}
void dfs_labels(int u, int p){
	label[u] = label_time++;
	update(1, 0, n - 1, label[u], arr[u]);
	if(bigChild[u] != -1) dfs_labels(bigChild[u], u);
	for(auto x: g[u]){
		if(x == p || x == bigChild[u]) continue;
		dfs_labels(x, u);
	}
}
int lca(int a, int b){
	if(depth[a] < depth[b]) swap(a, b);
	int d = depth[a] - depth[b];
	int u = k_th_ancestor(a, d);
	if(u == b) return u;
	for(int i = 19; i >= 0; i--){
		if(lca_lift[u][i] != lca_lift[b][i]){
			u = lca_lift[u][i];
			b = lca_lift[b][i];
		}
	}
	return lca_lift[b][0];
}
int k_th_ancestor(int u, int k){
	for(int i = 19; i >= 0; i--){
		if(u == -1) return u;
		if((1 << i) <= k){
			u = lca_lift[u][i];
			k -= (1 << i);
		}
	}
	return u;
}
int query_chain(int u, int v){
	int res = 0;
	while(depth[v] < depth[u]){
		int top = chain[u];
		if(depth[top] <= depth[v]){
			int diff = depth[u] - depth[v];
			top = k_th_ancestor(u, diff - 1);
		}
		res ^= get(1, 0, n - 1, label[top], label[u]);
		u = parent[top];
	}
	return res;
}
int query(int u, int v){
	int anc = lca(u, v);
	int res = query_chain(u, anc) ^ query_chain(v, anc);
	return res ^ get(1, 0, n - 1, label[anc], label[anc]);
}

void Solve(){
	int q;
	cin>>n>>q;
	for(int i = 0; i < n; i++)
		cin>>arr[i];
	init_arrays();
	for(int i = 1; i < n; i++){
		int u, v;
		cin>>u>>v;
		u--; v--;
		addEdge(u, v);
	}
	initTree(0);
	while(q--){
		int t, x, y;
		cin>>t>>x>>y;
		if(t == 1) update(1, 0, n - 1, label[x - 1], y);
		else cout<<query(x - 1, y - 1)<<nl;
	} 

}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	Solve();
}

Could someone plz explain why's there a difference verdict in my codes? Where did I get it wrong? I much appreciate it!

Full text and comments »

foundnt_Alice's blog