Untitled

 avatar
unknown
plain_text
a year ago
4.5 kB
6
Indexable
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
  
class UserSolution{
  
    class request{
        int uID;
        String fileName;
        int fileSize;
        ArrayList<Integer> path;
        request(int uID,String fileName,int fileSize){
            this.uID=uID;
            this.fileName=fileName;
            this.fileSize=fileSize;
            path=new ArrayList<Integer>();
        }
    }
    class user{
        ArrayList<Integer> child;
        HashMap<String,Boolean>map;
        user(){
            child = new ArrayList<Integer>();
            map = new HashMap<String, Boolean>();
        }
    }
    String CharToString(char[] x){
        int i=0;
        String s="";
        while(x[i]!=0){
            s+=x[i++];
        }
        return s;
    }
    user[] mapUser = new user[205];
    request[] mapRequest = new request[5005];
    int[][] mapBan = new int[205][205];
    HashMap<String, Integer> hmFile = new HashMap<String, Integer>();
    int n;
    public void init(int N, int mUID1[], int mUID2[], int mBandwidth[]){
  
        n=N;
        hmFile.clear();
        for(int i=0;i<=N;i++)
            mapUser[i] = new user();
        for(int i=0;i<N;i++){    
            int id1 = mUID1[i];
            int id2 = mUID2[i];
            mapBan[id1][id2] = mBandwidth[i];
            mapBan[id2][id1] = mBandwidth[i];
          
            mapUser[id1].child.add(id2);
            mapUser[id2].child.add(id1);
        }
    }
    public int share(int mUID, char mFilename[], int mFilesize){
  
        String fileName = CharToString(mFilename);
        hmFile.put(fileName,mFilesize);
        mapUser[mUID].map.put(fileName, true);
          
        //System.out.println(mapUser[mUID].map.size());
        return mapUser[mUID].map.size();
    }
    public int request(int mUID, char mFilename[], int mTID){
  
        String fileName = CharToString(mFilename);
        if(hmFile.get(fileName)==null) return -1;
        int fileSize = hmFile.get(fileName);
          
        boolean ok=false;
        int visit[] = new int[205];
        int par[] = new int[205];
        LinkedList<Integer> queue = new LinkedList<Integer>();
        int ans=205;
        //bfs
        queue.add(mUID);
        visit[mUID]=1;
        par[mUID]=-1;
          
        while(queue.isEmpty()==false){
            if(ok==true) break;
            int size = queue.size();
            while(size>0){
                int u = queue.poll();
                for(int it: mapUser[u].child){
                    if(visit[it]==0 && mapBan[u][it]>= fileSize){
                        visit[it]=1;
                        par[it]=u;
                        queue.add(it);
                        boolean check = mapUser[it].map.getOrDefault(fileName, false);
                        if(check==true)
                        {
                            ok=true;
                            ans=Math.min(ans, it);
                        }
                    }
                }
                size--;
            }
              
        }
        //kiem tra co tim dc user chua file hay ko? + luu path
        if(ok==false) 
            {
            //System.out.println(-1);
            return -1;
            }
        mapRequest[mTID] = new request(mUID, fileName, fileSize);
          
        int tmp = ans;
        while(par[tmp]!=-1){
            mapRequest[mTID].path.add(tmp);
            mapBan[tmp][par[tmp]]-=fileSize;
            mapBan[par[tmp]][tmp]-=fileSize;
            //mapUser[tmp].map.put(fileName,true);
            tmp = par[tmp];
        }
        //mapUser[mUID].map.put(fileName, true);
        mapRequest[mTID].path.add(mUID);
        //System.out.println(ans);
        return ans;
  
    }
    public int complete(int mTID){
        int id = mapRequest[mTID].uID;
        String fileName = mapRequest[mTID].fileName;
          
        for(int i=0;i<mapRequest[mTID].path.size()-1;i++){
            int it = mapRequest[mTID].path.get(i);
            int it_next = mapRequest[mTID].path.get(i+1);
            mapBan[it][it_next] += mapRequest[mTID].fileSize;
            mapBan[it_next][it] += mapRequest[mTID].fileSize;
            mapUser[it].map.put(fileName,true);
        }
        mapUser[id].map.put(fileName,true);
              
        //System.out.println(mapUser[id].map.size());
        return mapUser[id].map.size();
  
    }
  
}
Editor is loading...
Leave a Comment