sample
unknown
plain_text
a year ago
5.0 kB
8
Indexable
#include<unordered_map> #include<set> #include<iostream> #include<queue> using namespace std; typedef struct Info { int id; int s; int e; }tInfo; struct cmp_in { bool operator()(const tInfo &a,const tInfo &b)const { if (a.s == b.s) return a.id < b.id; return a.s < b.s; } }; struct cmp_out { bool operator()(const tInfo &a, const tInfo &b)const { if (a.e == b.e) return a.id < b.id; return a.e > b.e; } }; unordered_map<int, tInfo> umap; set<tInfo, cmp_in> set_in; void init() { umap.clear(); set_in.clear(); return; } int add(int mId, int mStart, int mEnd) { if (umap.find(mId) != umap.end()) { set_in.erase(umap[mId]); umap.erase(mId); } umap.insert({ mId,{mId,mStart,mEnd} }); set_in.insert({mId,mStart,mEnd}); return set_in.size(); } int remove(int mId) { set_in.erase(umap[mId]); umap.erase(mId); return set_in.size(); } int announce(int mDuration, int M) { priority_queue<tInfo, vector<tInfo>, cmp_out> pq_out; for (auto it : set_in) { if (it.e - it.s + 1 >= mDuration) pq_out.push(it); if ( !pq_out.empty() && pq_out.top().e - it.s + 1 < mDuration) pq_out.pop(); if (pq_out.size() >= M) return it.s; } return -1; } #include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; #define MAP_SIZE_MAX 350 #define MAX_NODES MAP_SIZE_MAX * MAP_SIZE_MAX int qx[MAX_NODES], qy[MAX_NODES], dist[MAX_NODES]; int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; vector<pair<int, int>> adj_mat[MAP_SIZE_MAX]; int matrix[MAP_SIZE_MAX][MAP_SIZE_MAX]; int dungeon[MAP_SIZE_MAX][MAP_SIZE_MAX]; int visited[MAP_SIZE_MAX][MAP_SIZE_MAX]; bool gate_exists[MAP_SIZE_MAX]; int dungeon_count = 0; int N; int go_until; void bfs(int row, int col) { int front = 0; int rear = 0; qx[rear] = row; dist[rear] = 0; qy[rear++] = col; visited[row][col] = dungeon_count; int parent_node = dungeon[row][col]; int u_row, u_col; int u_dist; int i; int temp_row, temp_col, temp_dest; while (front < rear) { u_row = qx[front]; u_dist = dist[front]; u_col = qy[front++]; for (i = 0; i < 4; i++) { if (u_dist + 1 > go_until) break; temp_row = u_row + dir[i][0]; temp_col = u_col + dir[i][1]; if (temp_row >= 0 && temp_col >= 0 && temp_row < N && temp_col < N && matrix[temp_row][temp_col] != 1 && visited[temp_row][temp_col] < dungeon_count) { if (dungeon[temp_row][temp_col] != -1) { temp_dest = dungeon[temp_row][temp_col]; adj_mat[temp_dest].push_back({ parent_node, u_dist + 1 }); adj_mat[parent_node].push_back({ temp_dest, u_dist + 1 }); } qx[rear] = temp_row; qy[rear] = temp_col; dist[rear++] = u_dist + 1; visited[temp_row][temp_col] = dungeon_count; } } } return; } void init(int N, int mMaxStamina, int mMap[MAP_SIZE_MAX][MAP_SIZE_MAX]) { go_until = mMaxStamina; for (int i = 0; i < MAP_SIZE_MAX; i++) { adj_mat[i].clear(); for (int j = 0; j < MAP_SIZE_MAX; j++) { dungeon[i][j] = -1; } } ::N = N; for (int i = 0; i < MAP_SIZE_MAX; i++) for (int j = 0; j < MAP_SIZE_MAX; j++) matrix[i][j] = mMap[i][j]; return; } void addGate(int mGateID, int mRow, int mCol) { gate_exists[mGateID] = 1; dungeon[mRow][mCol] = mGateID; dungeon_count++; bfs(mRow, mCol); return; } void removeGate(int mGateID) { gate_exists[mGateID] = 0; return; } int getMinTime(int mStartGateID, int mEndGateID) { int u_src, u_dist; int v_src, v_dist; int i; int qdist[MAP_SIZE_MAX]; for (i = 0; i < MAP_SIZE_MAX; i++) qdist[i] = INT_MAX; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({ 0,mStartGateID }); qdist[mStartGateID] = 0; while (!pq.empty()) { pair<int, int> u = pq.top(); pq.pop(); u_dist = u.first; u_src = u.second; if (u_src == mEndGateID) break; for (pair<int, int> v : adj_mat[u_src]) { v_src = v.first; v_dist = v.second; if (gate_exists[v_src] == 1 && qdist[v_src] > v_dist + qdist[u_src]) { qdist[v_src] = v_dist + qdist[u_src]; pq.push({ qdist[v_src], v_src }); } } } if (qdist[mEndGateID] == INT_MAX) return -1; return qdist[mEndGateID]; }
Editor is loading...
Leave a Comment