Untitled

import java.util.*;
 
class UserSolution {
    /*
     * Giua 2 user co 1 duong di (link) vo huong Moi duong di co so bandwidth
     * cho truoc
     */
    class User {
        HashSet<Integer> nei;
        HashSet<String> file;
        Node target[];
    }
 
    class Node {
        int sourceId, destinationID;
        ArrayList<Integer> paths;
    }
 
    class File {
        int size;
        HashSet<Integer> listUser = new HashSet<Integer>();
    }
 
    class Request {
        String nameFile;
        int sizeFile;
        ArrayList<Integer> paths;
    }
 
    class Queue {
        int head = 0, tail = 0;
        final int queueSize = 10000;
        int[] queue = new int[queueSize];
 
        void enqueue(int value) {
            queue[tail] = value;
            tail++;
            if (tail >= queueSize) {
                tail = 0;
            }
        }
 
        int dequeue() {
            int value = queue[head];
            head++;
            if (head >= queueSize) {
                head = 0;
            }
            return value;
        }
 
        boolean isEmpty() {
            return tail == head;
        }
    }
 
    public User U[];
    public HashMap<String, File> mapFile;
    public HashMap<Integer, Request> mapRequest;
    public int nUser;
    public int map[][];
 
    public void init(int N, int mU1[], int mU2[], int mBandwidth[]) {
        // Khai bao
        nUser = N;
        U = new User[N + 1];
        for (int i = 1; i <= N; i++) {
            U[i] = new User();
            U[i].file = new HashSet<String>();
            U[i].nei = new HashSet<Integer>();
            U[i].target = new Node[N + 1];
        }
        mapFile = new HashMap<String, UserSolution.File>();
        mapRequest = new HashMap<Integer, UserSolution.Request>();
        map = new int[N + 1][N + 1];
        for (int i = 0; i < N - 1; i++) {
            int a = mU1[i];
            int b = mU2[i];
            map[a][b] = mBandwidth[i];
            map[b][a] = mBandwidth[i];
            U[a].nei.add(b);
            U[b].nei.add(a);
        }
 
        // Luu duong di vao queue
        for (int i = 1; i <= N; i++) {
            Queue q = new Queue();
            int[] visited = new int[N + 1];
            q.enqueue(i);
            while (!q.isEmpty()) {
                int current = q.dequeue();
                visited[current] = 1;
                Node currentNode = null;
                if (U[i].target[current] != null) {
                    currentNode = U[i].target[current];
                }
 
                for (int next : U[current].nei) {
                    if (visited[next] == 0) {
                        q.enqueue(next);
                        Node n = new Node();
                        n.destinationID = next;
                        n.sourceId = i;
                        n.paths = new ArrayList<Integer>();
 
                        // Copy path cua currentNode vao n
                        if (currentNode != null) {
                            for (int path : currentNode.paths) {
                                n.paths.add(path);
                            }
                        }
                        n.paths.add(next);
                        // Add n vao target cua U[i]
                        U[i].target[next] = new Node();
                        U[i].target[next] = n;
                    }
                }
            }
        }
    }
 
    public int share(int Uid, char mFilename[], int mFilesize) {
        String fileName = CharToString(mFilename);
        // Luu file vao mapFile
        File file = mapFile.get(fileName);
        if (file == null) {
            file = new File();
            file.size = mFilesize;
            file.listUser.add(Uid);
            mapFile.put(fileName, file);
        } else {
            file.listUser.add(Uid);
            mapFile.put(fileName, file);
        }
 
        // Add file vao User
        U[Uid].file.add(fileName);
 
        return U[Uid].file.size();
    }
 
    public int request(int Uid, char mFilename[], int mTID) {
        String fileName = CharToString(mFilename);
        int res_soBuoc = 10000;
        int res_ID = 10000;
        int size = 0;
        // Ktra file duoc luu o User nao, va check duong di tu user do den Uid
 
        Request request = new Request();
        request.nameFile = fileName;
        request.sizeFile = size;
        request.paths = new ArrayList<Integer>();
        request.paths.add(Uid);
 
        File file = mapFile.get(fileName);
        if (file != null) {
            size = file.size;
            boolean flag = false;
            for (int user : file.listUser) {
                int count = U[Uid].target[user].paths.size();
                if (count < res_soBuoc) {
                    if (check(Uid, user, size)) {
                        flag = true;
                        res_soBuoc = count;
                        res_ID = user;
                    }
                } else if (count == res_soBuoc && res_ID > user) {
                    if (check(Uid, user, size)) {
                        flag = true;
                        res_soBuoc = count;
                        res_ID = user;
                    }
                }
            }
            // Add path vao request
            if (flag == true) {
                request.sizeFile = size;
                for (int path : U[Uid].target[res_ID].paths) {
                    request.paths.add(path);
                }
                // Cap nhat bandwidth
                for (int i = 1; i < request.paths.size(); i++) {
                    int a = request.paths.get(i);
                    int b = request.paths.get(i - 1);
                    map[a][b] -= size;
                    map[b][a] -= size;
                }
                // add request vao map
                mapRequest.put(mTID, request);
                return res_ID;
            }
        }
        mapRequest.put(mTID, request);
        return -1;
    }
 
    public int complete(int mTID) {
        Request request = mapRequest.get(mTID);
        int size = request.sizeFile;
        String fileName = request.nameFile;
        // Update bandwidth va add file vao user
        //Add user vao file
        if (size > 0) {
            for (int i = 1; i < request.paths.size(); i++) {
                int a = request.paths.get(i);
                int b = request.paths.get(i - 1);
                map[a][b] += size;
                map[b][a] += size;
                if (i == 1) {
                    U[b].file.add(fileName);
                    HashSet<Integer> list = mapFile.get(fileName).listUser;
                    list.add(b);
                }
                U[a].file.add(fileName);
                HashSet<Integer> list = mapFile.get(fileName).listUser;
                list.add(a);
            }
        }
        return U[request.paths.get(0)].file.size();
    }
 
    public String CharToString(char a[]) {
        String ret = "";
        int i = 0;
        while (i < a.length && a[i] != '\0') {
            ret += a[i];
            ++i;
        }
        return ret;
    }
 
    public boolean check(int Uid, int user, int size) {
        Node node = U[Uid].target[user];
        boolean flag = true;
        for (int i = 0; i < node.paths.size() && flag == true; i++) {
            if (i == 0) {
                if (map[node.paths.get(i)][node.sourceId] < size) {
                    flag = false;
                }
            } else {
                if (map[node.paths.get(i)][node.paths.get(i - 1)] < size) {
                    flag = false;
                }
            }
        }
        return flag;
    }
 
}