#define MAXL (10)
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<unordered_map>
using namespace std;
struct US {
string name;
int points;
}users[10001];
struct MS {
int id, par, points, root, uid;
bool isValid;
}msgs[50005];
unordered_map<string, int> userMap;
unordered_map<int, int> msgMap;
struct cmpu {
bool operator()(int a, int b) const {
if (users[a].points != users[b].points)
return users[a].points > users[b].points;
else
return users[a].name < users[b].name;
}
};
struct cmpm {
bool operator()(int a, int b) const {
if (msgs[a].points != msgs[b].points)
return msgs[a].points > msgs[b].points;
else
return msgs[a].id < msgs[b].id;
}
};
set<int, cmpu> userSet;
set<int, cmpm> postSet;
vector<int> msgGroup[50005];
int userIdx, msgIdx;
void init(){
userIdx = msgIdx = 0;
userSet.clear();
postSet.clear();
userMap.clear();
msgMap.clear();
return;
}
int findPar(int id) {
while (msgs[id].par != -1) {
id = msgs[id].par;
}
return id;
}
int updateUser(char uname[], int point) {
if (userMap.find(uname) == userMap.end()) {
userMap[uname] = userIdx;
users[userIdx].name = uname;
users[userIdx].points = 0;
userIdx++;
}
int id = userMap[uname];
userSet.erase(id);
users[id].points += point;
userSet.insert(id);
return id;
}
int writeMessage(char mUser[], int mID, int mPoint){
int uid = updateUser(mUser, mPoint);
int mid = msgIdx++;
msgMap[mID] = mid;
msgs[mid].id = mID;
msgs[mid].isValid = true;
msgs[mid].par = -1;
msgs[mid].points = mPoint;
msgs[mid].root = mPoint;
msgs[mid].uid = uid;
postSet.insert(mid);
msgGroup[mid].clear();
return users[uid].points;
}
int commentTo(char mUser[], int mID, int mTargetID, int mPoint){
int uid = updateUser(mUser, mPoint);
int mid = msgIdx++;
int parid = msgMap[mTargetID];
int rootid = findPar(parid);
msgMap[mID] = mid;
msgs[mid].id = mID;
msgs[mid].isValid = true;
msgs[mid].par = parid;
msgs[mid].points = mPoint;
msgs[mid].root = mPoint;
msgs[mid].uid = uid;
postSet.erase(rootid);
msgs[rootid].points += mPoint;
postSet.insert(rootid);
msgGroup[mid].clear();
msgGroup[parid].push_back(mid);
return msgs[rootid].points;
}
void rec_erase(int cur, int root) {
for (auto it : msgGroup[cur]) {
if (msgs[it].isValid) {
int uid = msgs[it].uid;
userSet.erase(uid);
users[uid].points -= msgs[it].root;
userSet.insert(uid);
msgs[root].points -= msgs[it].root;
rec_erase(it, root);
msgs[it].isValid = false;
}
}
}
int erase(int mID){
int mid = msgMap[mID];
int rootid = findPar(mid);
int uid = msgs[mid].uid;
postSet.erase(rootid);
rec_erase(mid, rootid);
msgs[mid].isValid = false;
msgs[rootid].points -= msgs[mid].root;
postSet.insert(rootid);
userSet.erase(uid);
users[uid].points -= msgs[mid].root;
userSet.insert(uid);
if (msgs[mid].par == -1) return users[uid].points;
else return msgs[rootid].points;
}
void getBestMessages(int mBestMessageList[]){
int i = 0;
for (auto it : postSet) {
mBestMessageList[i] = msgs[it].id;
i++;
if (i >= 5) break;
}
return;
}
void getBestUsers(char mBestUserList[][MAXL + 1]){
int i = 0;
for (auto it : userSet) {
int j = 0;
for (; j < users[it].name.size(); j++) {
mBestUserList[i][j] = users[it].name[j];
}
mBestUserList[i][j] = '\0';
i++;
if (i >= 5) break;
}
return;
}