UVa : 1357 :: Cells

Problem : Please find the problem here.

Summary : This can be solved using DFS. Considering the relation between the order in which a node and its ancestors are visited, we can set the in-time and out-time for each node in DFS when entering and leaving the node. Now a node u will be an ancestor of node v if and only if the in-time of u is less than the in-time of v and out-time of u is greater than the out-time of v.

Code : The key thing for me to learn in this problem was to store the first child of every node, and during DFS iterate from this first child to (first_child + total_child). My previous solution was correct but was giving TLE verdict, then after I discoverd this trick to only store the first child for the given node.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 3e5, mxM = 2e7;
int n, m, c[mxN], b[mxN], tin[mxM], tout[mxM], cnt;
vector<int> adj[mxN];
bool vis[mxM];

void dfs(int u){
	tin[u] = cnt++;
	for(int v = b[u]; v < c[u]+b[u]; v++){
		if(v >= n){
			tin[v] = cnt++;
			tout[v] = cnt++;
		}
		else{
			dfs(v);
		}
	}
	tout[u] = cnt++;
}

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> c[i];
		if(i == 0) b[i] = 1;
		else b[i] = b[i-1]+c[i-1];
	}
	/*
	for(int i = 0; i < n; i++){
		cout << b[i] << ' ';
	}
	cout << '\n';
	*/
	cnt = 0;
	memset(tin, 0, sizeof(tin));
	memset(tout, 0, sizeof(tout));
	dfs(0);
	cin >> m;
	for(int i = 0, u, v; i < m; i++){
		cin >> u >> v;
		cout << ((tin[u]<tin[v] && tout[v]<tout[u])?"Yes\n":"No\n");
	}
}
int main()
{
	int t;
	cin >> t;
	for(int k = 1; k <= t; k++){
		if(k != 1){
			cout << "\n";
		}
		cout << "Case " << k << ":\n";
		solve();
	}	
	return 0;
}