Untitled

#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <stdexcept>
 
 
using namespace std;
 
 
#define TRAVEL 2 // 0:DFS, 1:DFS(Recursive), 2:BFS
#define STRUCTURE 1 // 0:Adj_Matrix, 1:Adj_List
 
 
#define MAX_TRANSFER 5002
#define MAX_USER 205
#define MAX_FILETYPE 5002
 
 
struct Link {
    int bandwidth;
    int used = 0;
};
 
 
struct User {
#if STRUCTURE==0
    int LinkTo[MAX_USER];
#elif STRUCTURE==1
    int Adjs[MAX_USER];
    int LinkToAdjs[MAX_USER];
    int numAdj;
#endif
    bool Has[MAX_FILETYPE];
    int numDownFile;
 
 
    int parent;  // temp for request
    int linkToParent;  // temp for request
};
 
 
struct Transfer {
    int fileType;
    int requester;
    bool complete;
    int InvolvedLinks[MAX_USER];
    int InvolvedUsers[MAX_USER];
    int numInvolvedLink;
};
 
 
int NumUser;
Link Links[MAX_USER];
User Users[MAX_USER];
Transfer Transfers[MAX_TRANSFER];
int FileSizes[MAX_FILETYPE];
unordered_map<string, int> FileHash;  // filename, fileType
 
 
int testCount = 0;
 
 
 
 
void init(int N, int mUID1[], int mUID2[], int mBandwidth[]) {
    NumUser = N;
 
 
    FileHash.clear();
    for (int i = 1; i <= NumUser; i++) {
#if STRUCTURE==0
        for (int j = 1; j <= NumUser; j++) {
            Users[i].LinkTo[j] = -1;
        }
#elif STRUCTURE==1
        Users[i].numAdj = 0;
#endif
        Users[i].numDownFile = 0;
    }
    for (int i = 0; i <= NumUser - 2; i++) {
        Links[i].bandwidth = mBandwidth[i];
        Links[i].used = 0;
#if STRUCTURE==0
        Users[mUID1[i]].LinkTo[mUID2[i]] = i;
        Users[mUID2[i]].LinkTo[mUID1[i]] = i;
#elif STRUCTURE==1
        Users[mUID1[i]].Adjs[Users[mUID1[i]].numAdj] = mUID2[i];
        Users[mUID1[i]].LinkToAdjs[Users[mUID1[i]].numAdj] = i;
        Users[mUID1[i]].numAdj++;
 
 
        Users[mUID2[i]].Adjs[Users[mUID2[i]].numAdj] = mUID1[i];
        Users[mUID2[i]].LinkToAdjs[Users[mUID2[i]].numAdj] = i;
        Users[mUID2[i]].numAdj++;
#endif
    }
    for (int i = 0; i < MAX_TRANSFER; i++) {
        Transfers[i].complete = false;
        Transfers[i].numInvolvedLink = 0;
    }
 
 
    testCount++;
}
 
 
int share(int mUID, char mFilename[], int mFilesize) {
    if (FileHash.count(mFilename)) {
        int fileType = FileHash.find(mFilename)->second;
        if (!Users[mUID].Has[fileType]) {
            Users[mUID].Has[fileType] = true;
            Users[mUID].numDownFile++;
        }
    }
    else {
        int newFileType = (int)FileHash.size();
        FileHash.insert({ mFilename, newFileType });
        for (int i = 1; i <= NumUser; i++) {
            Users[i].Has[newFileType] = (i == mUID ? true : false);
        }
        Users[mUID].numDownFile++;
        FileSizes[newFileType] = mFilesize;
    }
    return Users[mUID].numDownFile;
}
 
 
static int fileType, fileSize, targetUid, minDepth;
 
 
#if TRAVEL==1
void dfs(int curUID, int curDepth) {
    if (curDepth > minDepth) {
        return;
    }
 
 
    if (Users[curUID].Has[fileType]) {        
        if (curDepth < minDepth) {
            minDepth = curDepth;
            targetUid = curUID;
        }
        else if (curDepth == minDepth) {
            if (curUID < targetUid) {
                targetUid = curUID;
            }
        }
        return;
    }
#if STRUCTURE==0
    for (int i = 1; i <= NumUser; i++) {
        int link = Users[curUID].LinkTo[i];
        if (link == -1) {
            continue;
        }
        int nextBandwith = Links[link].bandwidth;
        int nextUsed = Links[link].used;
        int nextUID = i;
 
 
        if (nextBandwith - nextUsed >= fileSize && nextUID != Users[curUID].parent) {
            Users[nextUID].parent = curUID;
            Users[nextUID].linkToParent = link;
            dfs(nextUID, curDepth + 1);
        }
    }
#elif STRUCTURE==1
    for (int i = 0; i < Users[curUID].numAdj; i++) {
        int nextBandwith = Links[Users[curUID].LinkToAdjs[i]].bandwidth;
        int nextUsed = Links[Users[curUID].LinkToAdjs[i]].used;
        int nextUID = Users[curUID].Adjs[i];
 
 
        if (nextBandwith - nextUsed >= fileSize && nextUID != Users[curUID].parent) {
            Users[nextUID].parent = curUID;
            Users[nextUID].linkToParent = Users[curUID].LinkToAdjs[i];
            dfs(nextUID, curDepth + 1);
        }
    }
#endif
}
#endif
 
 
int request(int mUID, char mFilename[], int mTID) {
    if (!FileHash.count(mFilename)) {
        Transfers[mTID].requester = mUID;
        Transfers[mTID].complete = true;
        return -1;
    }
 
 
    fileType = FileHash.find(mFilename)->second;
    fileSize = FileSizes[fileType];
 
 
    targetUid = NumUser + 1;
    minDepth = NumUser;
    Users[mUID].parent = -1;
    Users[mUID].linkToParent = -1;
 
 
#if TRAVEL==1
    dfs(mUID, 0);
#else
#if TRAVEL==0
    stack< pair<int, int> > s;  // user, depth
    s.push({ mUID, 0 });
#elif TRAVEL==2
    queue< pair<int, int> > q;  // user, depth
    q.push({ mUID, 0 });
#endif
 
 
#if TRAVEL==0
    while (!s.empty()) {
        int curUID = s.top().first;
        int curDepth = s.top().second;
        s.pop();
#elif TRAVEL==2
    while (!q.empty()) {
        int curUID = q.front().first;
        int curDepth = q.front().second;
        q.pop();
#endif
        if (curDepth > minDepth) {
            continue;
        }
 
 
        if (Users[curUID].Has[fileType]) {
            if (curDepth < minDepth) {
                minDepth = curDepth;
                targetUid = curUID;
            }
            else if (curDepth == minDepth) {
                if (curUID < targetUid) {
                    targetUid = curUID;
                }
            }
            continue;
        }
#if STRUCTURE==0
        for (int i = 1; i <= NumUser; i++) {
            int link = Users[curUID].LinkTo[i];
            if (link == -1) {
                continue;
            }
            int nextBandwith = Links[link].bandwidth;
            int nextUsed = Links[link].used;
            int nextUID = i;
 
 
            if (nextBandwith - nextUsed >= fileSize && nextUID != Users[curUID].parent) {
                Users[nextUID].parent = curUID;
                Users[nextUID].linkToParent = link;
#elif STRUCTURE==1
        for (int i = 0; i < Users[curUID].numAdj; i++) {
            int nextBandwith = Links[Users[curUID].LinkToAdjs[i]].bandwidth;
            int nextUsed = Links[Users[curUID].LinkToAdjs[i]].used;
            int nextUID = Users[curUID].Adjs[i];
 
 
            if (nextBandwith - nextUsed >= fileSize && nextUID != Users[curUID].parent) {
                Users[nextUID].parent = curUID;
                Users[nextUID].linkToParent = Users[curUID].LinkToAdjs[i];
#endif
#if TRAVEL==0
                s.push({ nextUID, curDepth + 1 });
#elif TRAVEL==2
                q.push({ nextUID, curDepth + 1 });
#endif
            }
        }
    }
#endif
 
 
    // store transfer
    Transfers[mTID].fileType = fileType;
    Transfers[mTID].requester = mUID;
 
 
    if (targetUid == NumUser + 1) {
        Transfers[mTID].complete = true;
        return -1;
    }
 
 
    // trace info
    int curLid;
    int curUid = targetUid;
    while (Users[curUid].linkToParent != -1) {
        curLid = Users[curUid].linkToParent;
        Links[curLid].used += fileSize;
 
 
        curUid = Users[curUid].parent;
        Transfers[mTID].InvolvedLinks[Transfers[mTID].numInvolvedLink] = curLid;
        Transfers[mTID].InvolvedUsers[Transfers[mTID].numInvolvedLink++] = curUid;
    }
 
 
    return targetUid;
}
 
 
int complete(int mTID) {
    int requester = Transfers[mTID].requester;
    int filesize = FileSizes[Transfers[mTID].fileType];
    int fileType = Transfers[mTID].fileType;
 
 
    if (Transfers[mTID].complete) {
        return Users[requester].numDownFile;
    }
 
 
    for (int i = 0; i < Transfers[mTID].numInvolvedLink; i++) {
        Links[Transfers[mTID].InvolvedLinks[i]].used -= filesize;
        i = i;
    }
 
 
    for (int i = 0; i < Transfers[mTID].numInvolvedLink; i++) {
        int curUID = Transfers[mTID].InvolvedUsers[i];
        if (!Users[curUID].Has[fileType]) {
            Users[curUID].Has[fileType] = true;
            Users[curUID].numDownFile++;
        }
    }
 
 
    Transfers[mTID].complete = true;
 
 
    return Users[requester].numDownFile;
}