Submission #286381

#	Time	Username	Problem	Language	Result	Execution time	Memory
286381		Puddlestomps	Mecho (IOI09_mecho)	C++17	88 / 100	524 ms	59536 KiB

mecho

#include "bits/stdc++.h"

using namespace std;

typedef long long BEEG;
typedef unsigned long long uBEEG;

struct Node
{
    int x, y, beedist = INT_MAX, dist = INT_MAX, time = INT_MAX, par = INT_MAX, check = INT_MAX;
    vector<int> edges;

    Node(int x, int y) : x(x), y(y) {}
};


constexpr int MAXN = 800;
int N, S, start = -1, home = -1, maxbee = -1;
array<array<int, MAXN>, MAXN> board;
vector<Node> nodes;
//vector<int> hives;

void connect(int node, int x, int y)
{
    if(x > 0)
    {
        int left = board[y][x - 1];
        if(left != -1)
        {
            nodes[node].edges.push_back(left);
            nodes[left].edges.push_back(node);
        }
    }

    if(y > 0)
    {
        int up = board[y - 1][x];
        if(up != -1)
        {
            nodes[node].edges.push_back(up);
            nodes[up].edges.push_back(node);
        }
    }
}

queue<int> hives;

void hivebfs()
{
    while(!hives.empty())
    {
        const Node& top = nodes[hives.front()];
        hives.pop();

        for(int i : top.edges)
        {
            if(nodes[i].beedist != INT_MAX || i == home) continue;
            
            nodes[i].beedist = top.beedist + 1;
            
            hives.push(i);

            maxbee = top.beedist + 1;
        }
    }
}

struct Djik
{
    int node;
    int time;
    int dist;
    int check;
    int par;

    Djik(int a, int time, int dist, int check, int par) : node(a), time(time), dist(dist), check(check), par(par) {}

    bool operator<(const Djik& rhs) const
    {
        if(time == rhs.time)
        {
            if(check == rhs.check)
            {
                if(dist == rhs.dist) return node < rhs.node;
                return dist > rhs.dist;
            }
            return check < rhs.check;
        }
        return time < rhs.time;
    }
};

void djikstra()
{
    priority_queue<Djik> pq;
    pq.emplace(home, INT_MAX, 0, 0, INT_MAX);

    while(!pq.empty())
    {
        Djik top = pq.top();
        int n = top.node;
        int d = top.dist;
        int t = top.time;
        int c = top.check;
        int p = top.par;

        pq.pop();

        if(nodes[n].dist != INT_MAX) continue;
        
        nodes[n].dist = d;
        nodes[n].par = p;
        nodes[n].time = t;
        nodes[n].check = c;

        for(int i : nodes[n].edges)
        {
            if(nodes[i].dist != INT_MAX) continue;

            int check = c;
            int time = t;

            if(d >= c + S)
            {
                check = d;
                time--;
            }

            if(nodes[i].beedist < time)
            {
                time = nodes[i].beedist;
                check = d;
            }

            pq.emplace(i, time, d + 1, check, n);
        }
    }
}

int main()
{
    array<int, MAXN> temp;
    temp.fill(-1);
    board.fill(temp);

    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> S;
    nodes.reserve(N*N);

    string line;
    for(int y = 0; y < N; y++)
    {
        cin >> line;
        for(int x = 0; x < N; x++)
        {
            switch(line[x])
            {
            case 'M':
                start = nodes.size();
            case 'G':
                board[y][x] = nodes.size();
                nodes.emplace_back(x, y);
                connect(nodes.size() - 1, x, y);
                break;
            case 'D':
                home = nodes.size();
                board[y][x] = nodes.size();
                nodes.emplace_back(x, y);
                connect(nodes.size() - 1, x, y);
                break;
            case 'H':
                hives.push(nodes.size());
                board[y][x] = nodes.size();
                nodes.emplace_back(x, y);
                nodes.back().beedist = 0;
                connect(nodes.size() - 1, x, y);
                break;
            }
        }
    }

    hivebfs();

    djikstra();

#if 0
    for(int i = 0; i < nodes.size(); i++)
    {
        cerr << "Node " << i << ": ";
        cerr << nodes[i].x << ", " << nodes[i].y << " | ";
        cerr << "Beedist: " << nodes[i].beedist << " | ";
        cerr << "Time: " << nodes[i].time << " | ";
        cerr << "Dist: " << nodes[i].dist << " | ";
        cerr << "Check: " << nodes[i].check << " | ";
        cerr << "Par: " << nodes[i].par << "\n";
    }
#endif
    cout << nodes[start].time - 1 << "\n";
}

• Subtask 1: 88 / 100