confusion in code

[GameOn]

i was stuck at 1 problem in which we need to implement bfs on topologiacally sorted graph(input graph was not sorted initially also this was prescribed {to sort}) in which we need to give the total wieght of graph and leaves have wt=1 and node ahs weight =sum of weights of its childs
i find this guy code in which i was confused about his use of memo array.

i64 memo[50];

struct CorporationSalary {
i64 f(const vector<string>& v, int n, int k) {
i64& total = memo[k]; if (total != -1) return total;
bool found = false;
total = 0;
for (int i = 0; i < n; ++i) if (i != k && v[k][i] == 'Y') {
total += f(v, n, i); found = true;
}
if (!found) total = 1;
return total;
}

i64 totalSalary(vector<string> v) {
const int n = (int)v.size();
memset(memo, -1, sizeof(memo));
i64 total = 0;
for (int k = 0; k < n; ++k)
total += f(v, n, k);
return total;
}
};

here i64 is long long
he first initialise all its values to -1 and never change in the programme
so whats the use of this line
//i64& total = memo[k]; if (total != -1) return total;

as memo[k] is always -1 so as total
also i was not able to understand whats this "i64&" means which i think is the key to my solution

code is exceeding time limit without using this memo array

[helios]

i64 & declares a reference to an i64. A reference can be thought of as an alias to the variable it was assigned. If you know about pointers, they're exactly like them, except you don't need to put the * in front of them to dereference them, they can't be null, and they have to be initialized when they're declared or the compiler complains.

[GameOn]

ok that means i64& totol is storing the address of memo[k] and if(total!=-1) is checking that if memo[k]!=-1(as you told that we need not to put * to derefence them)
if yes then we can do it directly whats the use of i64& total? i mean check if(memo[k]!=-1)
also, my main question was as all elements of memo are -1 as hes using memset in main function and hes is not changing it throughout the programme so whats the using of that if statement
//i64& total = memo[k]; if (total != -1) return total; coz we know that total alwas return -1.
well i know there is some use of that statement but please tell me if you can

[helios]

if yes then we can do it directly whats the use of i64& total?

In this case, absolutely none. It's just one more level of reference to dereference.

If you're certain it doesn't change, then it's pointless, obviously. Of course, you may also be missing something and should perhaps ask.

[GameOn]

so it means i can write the fuction as

i64 d(const vector<string>& v, int n, int k) {
bool found = false;
i64 total = 0;
for (int i = 0; i < n; ++i) if (i != k && v[k][i] == 'Y') {
total += d(v, n, i); found = true;
}
if (!found) total = 1;
return total;
}
well i did that its working fine but it is exceeding time limit for some test cases hence rejected.
seems like first code is avoiding some useless calculations i.e. theres is some sort of memoisation in that code (i am really bad in that concept) can you please figure out that in code.
for your reference heres the actual question
http://www.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179

and the code of that guy

http://www.topcoder.com/stat?c=problem_solution&rm=297785&rd=12179&pm=9824&cr=22653044

[helios]

The URL requires login.

i64 d(const vector<string>& v, int n, int k) {
	bool found = false;
	i64 total = 0;
	for (int i = 0; i < n; ++i)
		if (i != k && v[k][i] == 'Y') {
			total += d(v, n, i);
			found = true;
		}
	if (!found)
		total = 1;
	return total;
} 

If you're going for performance, there's a few problems with this code:
1. The function is recursive.
2. You're passing a vector of strings, each access, both to the vector and each string, has overhead for bounds checking.
3. total is a 64-bit variable. Unless you're certain that the target is a 64-bit processor, it's best to be conservative and use [unsigned] long, which is often as big as the registers use by the CPU.
4. found is unnecessary. You could replace the condition at the end with if (!total)