Submission #286381

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
286381	2020-08-30T10:51:56 Z	Puddlestomps	Mecho (IOI09_mecho)	C++17	88 / 100	524 ms	59536 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2816 KB	Output is correct
2	Correct	2 ms	2816 KB	Output is correct
3	Correct	2 ms	2796 KB	Output is correct
4	Correct	2 ms	2816 KB	Output is correct
5	Correct	2 ms	2816 KB	Output is correct
6	Correct	2 ms	2816 KB	Output is correct
7	Correct	470 ms	59356 KB	Output is correct
8	Correct	2 ms	2816 KB	Output is correct
9	Correct	2 ms	2816 KB	Output is correct
10	Correct	2 ms	2816 KB	Output is correct
11	Correct	2 ms	2816 KB	Output is correct
12	Correct	2 ms	3072 KB	Output is correct
13	Correct	3 ms	3072 KB	Output is correct
14	Incorrect	4 ms	3200 KB	Output isn't correct
15	Correct	2 ms	2816 KB	Output is correct
16	Correct	2 ms	2816 KB	Output is correct
17	Correct	2 ms	2816 KB	Output is correct
18	Correct	2 ms	2816 KB	Output is correct
19	Correct	4 ms	2944 KB	Output is correct
20	Correct	2 ms	2848 KB	Output is correct
21	Correct	2 ms	2944 KB	Output is correct
22	Correct	3 ms	2944 KB	Output is correct
23	Correct	2 ms	2944 KB	Output is correct
24	Correct	3 ms	2944 KB	Output is correct
25	Correct	2 ms	3072 KB	Output is correct
26	Correct	3 ms	3072 KB	Output is correct
27	Correct	2 ms	3072 KB	Output is correct
28	Correct	2 ms	3072 KB	Output is correct
29	Correct	2 ms	3072 KB	Output is correct
30	Correct	2 ms	3072 KB	Output is correct
31	Correct	3 ms	3072 KB	Output is correct
32	Correct	3 ms	3072 KB	Output is correct
33	Correct	14 ms	8192 KB	Output is correct
34	Correct	15 ms	8192 KB	Output is correct
35	Correct	39 ms	10880 KB	Output is correct
36	Correct	18 ms	9856 KB	Output is correct
37	Correct	19 ms	9856 KB	Output is correct
38	Correct	54 ms	13312 KB	Output is correct
39	Correct	27 ms	11776 KB	Output is correct
40	Correct	24 ms	11776 KB	Output is correct
41	Correct	67 ms	16128 KB	Output is correct
42	Correct	28 ms	13944 KB	Output is correct
43	Correct	28 ms	13824 KB	Output is correct
44	Correct	82 ms	19192 KB	Output is correct
45	Correct	33 ms	16228 KB	Output is correct
46	Correct	38 ms	16128 KB	Output is correct
47	Correct	104 ms	22648 KB	Output is correct
48	Correct	42 ms	18680 KB	Output is correct
49	Correct	51 ms	18644 KB	Output is correct
50	Correct	129 ms	26488 KB	Output is correct
51	Correct	48 ms	21496 KB	Output is correct
52	Correct	47 ms	21496 KB	Output is correct
53	Correct	151 ms	30548 KB	Output is correct
54	Correct	56 ms	24440 KB	Output is correct
55	Correct	56 ms	24440 KB	Output is correct
56	Correct	171 ms	34936 KB	Output is correct
57	Correct	62 ms	27640 KB	Output is correct
58	Correct	62 ms	27768 KB	Output is correct
59	Correct	203 ms	39708 KB	Output is correct
60	Correct	69 ms	31096 KB	Output is correct
61	Correct	69 ms	31032 KB	Output is correct
62	Correct	228 ms	44792 KB	Output is correct
63	Correct	149 ms	36344 KB	Output is correct
64	Correct	155 ms	36344 KB	Output is correct
65	Correct	146 ms	36532 KB	Output is correct
66	Correct	158 ms	36420 KB	Output is correct
67	Incorrect	146 ms	36304 KB	Output isn't correct
68	Correct	160 ms	36344 KB	Output is correct
69	Correct	157 ms	36344 KB	Output is correct
70	Correct	168 ms	36476 KB	Output is correct
71	Correct	164 ms	36504 KB	Output is correct
72	Correct	161 ms	36472 KB	Output is correct
73	Correct	430 ms	58360 KB	Output is correct
74	Correct	524 ms	59536 KB	Output is correct
75	Correct	438 ms	58584 KB	Output is correct
76	Correct	441 ms	58488 KB	Output is correct
77	Correct	436 ms	58616 KB	Output is correct
78	Incorrect	435 ms	58620 KB	Output isn't correct
79	Correct	519 ms	59532 KB	Output is correct
80	Correct	428 ms	58572 KB	Output is correct
81	Correct	420 ms	58352 KB	Output is correct
82	Correct	462 ms	58836 KB	Output is correct
83	Correct	425 ms	58488 KB	Output is correct
84	Correct	493 ms	59408 KB	Output is correct
85	Correct	443 ms	58836 KB	Output is correct
86	Correct	420 ms	58488 KB	Output is correct
87	Correct	460 ms	58836 KB	Output is correct
88	Correct	453 ms	58644 KB	Output is correct
89	Correct	474 ms	59524 KB	Output is correct
90	Correct	460 ms	58952 KB	Output is correct
91	Correct	470 ms	59524 KB	Output is correct
92	Correct	455 ms	58952 KB	Output is correct