sample

 avatar
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