Untitled

/*

1. logn
2. logn
3. k+logn

*/

#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
#include <queue>
using namespace std;

struct Record {
	int customerID;
	int revenue;
	vector<int> referWho;
	Record(): customerID(-1), revenue(0), referWho() {} // !!!!!!!!!!!! need this default constructor
	Record(int customerID, int revenue, vector<int> referWho): customerID(customerID), revenue(revenue), referWho(referWho) { }
	bool operator<(const Record &that) const {
		return revenue < that.revenue;
	}
};


class CustomerRevenue {
public:
	void insert(int revenue){
		vector<int> empty;
		Record r = Record(customerCounter, revenue, empty);
		mySet.emplace(r);
		m[customerCounter] = r;
		customerCounter += 1;
	}

	void insert(int revenue, int referID){
		vector<int> empty;
		Record r = Record(customerCounter, revenue, empty);
		mySet.emplace(r);
		m[customerCounter] = r;
		

		Record referred = m[referID];
		vector<int> referrals = referred.referWho;
		referrals.push_back(customerCounter);
		Record newRecord = Record(referID, referred.revenue, referrals);
		m[referID] = newRecord;
		mySet.emplace(newRecord);
		mySet.erase(referred);

		customerCounter += 1;
	}

	int getRevenue(int customerId, int max_depth){
		int total = 0;

		if(max_depth == 0){
			return m[customerId].revenue;
		}

		vector<int> customers;
		queue<int> q;
		q.push(customerId);
		for(int i = 0; i <= max_depth; i++){ // <= ??????
			int size = q.size();
			for(int j = 0; j < size; j++){
				int top = q.front();
				q.pop();
				customers.push_back(top);

				vector<int> referrals = m[top].referWho;
				for(int k = 0; k < referrals.size(); k++){
					q.push(referrals[k]);
				}
			}
		}


		for(int i = 0; i < customers.size(); i++){
			total += m[customers[i]].revenue;
		}

		return total;
	}

private:
	set<Record> mySet;
	unordered_map<int, Record> m; // customerID, Record // 
	int customerCounter = 0;

};

int main(){
	CustomerRevenue system;
	system.insert(10);
	system.insert(20, 0);
	system.insert(30, 1);
	system.insert(40, 2);
	system.insert(50, 3);
	system.insert(60, 0);
	int result = system.getRevenue(0, 2);
	cout << "result = " << result << endl; // 120
	

	return 0;

}