Untitled
plain_text
2 months ago
4.5 kB
1
Indexable
Never
#define MAX 10000 struct Node{ int row; int col; int infect; int next[4]; }Point[50001]; struct User{ int N; int Node[101]; }user[1001]; int hTable[4][MAX*2]; void init() { for (int i = 0; i < 4; i++) { for (int j = 0; j < MAX*2; j++) { hTable[i][j]=0; } } for (int i = 0; i < 1001; i++) { user[i].N=0; } } void addPlace(int pID, int r, int c) { Point[pID].row=r; Point[pID].col=c; Point[pID].infect=0; Point[pID].next[0]=hTable[0][r]; hTable[0][r]=pID; Point[pID].next[1]=hTable[1][c]; hTable[1][c]=pID; Point[pID].next[2]=hTable[2][r+c]; hTable[2][r+c]=pID; Point[pID].next[3]=hTable[3][r-c+MAX]; hTable[3][r-c+MAX]=pID; } void deleteCustome(int pID,int id,int h){ int tmp = hTable[id][h]; int pre = 0; while(tmp){ if(tmp == pID){ if(pre == 0) hTable[id][h] = Point[hTable[id][h]].next[id]; Point[pre].next[id] =Point[tmp].next[id]; } pre=tmp; tmp=Point[tmp].next[id]; } } void removePlace(int pID) { deleteCustome(pID,0,Point[pID].row); deleteCustome(pID,1,Point[pID].col); deleteCustome(pID,2,Point[pID].row + Point[pID].col); deleteCustome(pID,3,Point[pID].row - Point[pID].col + MAX); } int check(int pID, int dir){ int r = Point[pID].row; int c = Point[pID].col; int id = 0; int temp = MAX; int tmp; switch (dir) { case 0: tmp = hTable[1][c]; while(tmp) { if(!Point[tmp].infect && Point[tmp].row < r && (r - Point[tmp].row) < temp) { id = tmp; temp = r - Point[tmp].row; } tmp = Point[tmp].next[1]; } break; case 1: tmp = hTable[2][r+c]; while(tmp) { if(!Point[tmp].infect && Point[tmp].row < r && (r - Point[tmp].row) < temp) { id = tmp; temp = r - Point[tmp].row; } tmp = Point[tmp].next[2]; } break; case 2: tmp = hTable[0][r]; while(tmp) { if(!Point[tmp].infect && Point[tmp].col > c && (Point[tmp].col - c) < temp) { id = tmp; temp = Point[tmp].col - c; } tmp = Point[tmp].next[0]; } break; case 3: tmp = hTable[3][r - c+ MAX]; while(tmp) { if(!Point[tmp].infect && Point[tmp].col > c && (Point[tmp].col - c) < temp) { id = tmp; temp = Point[tmp].col - c; } tmp = Point[tmp].next[3]; } break; case 4: tmp = hTable[1][c]; while(tmp) { if(!Point[tmp].infect && Point[tmp].row > r && (Point[tmp].row - r) < temp) { id = tmp; temp = Point[tmp].row - r; } tmp = Point[tmp].next[1]; } break; case 5: tmp = hTable[2][r+c]; while(tmp) { if(!Point[tmp].infect && Point[tmp].row > r && (Point[tmp].row - r) < temp) { id = tmp; temp = Point[tmp].row - r; } tmp = Point[tmp].next[2]; } break; case 6: tmp = hTable[0][r]; while(tmp) { if(!Point[tmp].infect && Point[tmp].col < c && (c - Point[tmp].col) < temp) { id = tmp; temp = c - Point[tmp].col; } tmp = Point[tmp].next[0]; } break; case 7: tmp = hTable[3][r-c+MAX]; while(tmp) { if(!Point[tmp].infect && Point[tmp].col < c && (c - Point[tmp].col) < temp) { id = tmp; temp = c - Point[tmp].col; } tmp = Point[tmp].next[3]; } break; default: break; } return id; } void contactTracing(int uID, int visitNum, int moveInfo[], int visitList[]) { int pID = moveInfo[0]; visitList[0] = moveInfo[0]; user[uID].Node[user[uID].N++] = moveInfo[0]; for(int i = 1; i < visitNum; i++) { int next = check(pID, moveInfo[i]); visitList[i] = pID = next; user[uID].Node[user[uID].N++] = next; } for(int i = 0; i < visitNum; i++) Point[visitList[i]].infect = 1; } void disinfectPlaces(int uID) { for(int i =0; i < user[uID].N; i++) { Point[user[uID].Node[i]].infect = 0; } }