Submission #338584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338584	2020-12-23T13:08:57 Z	blue	Mecho (IOI09_mecho)	C++11	53 / 100	806 ms	65540 KB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

/*
Mecho takes at most S steps per minute.
Bees spread every minute.

(*) Restatement:
Mecho takes at most 1 step every minute.
Bees spread at the end of every S'th minute.

For every location, compute the number of minutes before the location cannot be occupied anymore.
For trees and hives this number is zero.
Consider hives as -1
Consider
*/
int N, S;
int grid[800*800]; //the number of minutes before this location cannot be occupied anymore.
int mecho;
int home;
//LOOKS GOOD

int INF = 2e9;

int binary_search(int a, int b)
{
    // cout << "____________________________\n binary search " << a << ' ' << b << '\n';
    int m = (a+b)/2+1;
    if(a == b) m = a;

    vector<int> dist(N*N, INF);
    //cout << mecho << ' ' << dist[mecho] << ' ' << home << '\n';

    queue<int> tbv;
    dist[mecho] = m;
    tbv.push(mecho);


    int u;
    while(!tbv.empty())
    {
        u = tbv.front();
    //    cout << u << ' ' << dist[u] << '\n';
        tbv.pop();

        vector<int> edge; //check down
        edge.clear();
        if(u % N != 0) edge.push_back(u-1);
        if(u % N != N-1) edge.push_back(u+1);
        if(u >= N) edge.push_back(u-N);
        if(u < N*(N-1)) edge.push_back(u+N);

        for(int v: edge)
        {
            if(dist[v] != INF) continue;
            if(dist[u] + 1 >= grid[v]) continue;
            dist[v] = dist[u] + 1;
            tbv.push(v);
        }
    }

    if(a == b)
    {
        if(dist[home] == INF) return -1;
        else return a/S;
    }
    else
    {
        if(dist[home] == INF) return binary_search(a, m-1);
        else return binary_search(m, b);
    }
}

int main()
{
    char c;
    cin >> N >> S;

    for(int i = 0; i < N*N; i++)
    {
        cin >> c;
        if(c == 'T') grid[i] = 0;
        else if(c == 'G') grid[i] = INF;
        else if(c == 'M')
        {
            grid[i] = INF;
            mecho = i;
        }
        else if(c == 'D')
        {
            grid[i] = 0;
            home = i;
        }
        else grid[i] = -1;
    }

    vector<int> visit(N*N, 0);

    queue<int> tbv;

    for(int i = 0; i < N*N; i++)
    {
        if(grid[i] != -1) continue;
        grid[i] = 0;
        tbv.push(i);
        visit[i] = 1;
    }

    while(tbv.size() > 0)
    {
        int u = tbv.front();
        tbv.pop();

        vector<int> edge;
        edge.clear();
        if(u % N > 0) edge.push_back(u-1);
        if(u % N < N-1) edge.push_back(u+1);
        if(u >= N) edge.push_back(u-N);
        if(u < N*(N-1)) edge.push_back(u+N);

        for(int v: edge)
        {
            if(visit[v]) continue;
            if(grid[v] > grid[u] + S)
            {
                grid[v] = grid[u] + S;
                tbv.push(v);
            }
        }
    }

    grid[home] = INF;

    // for(int i = 0; i < N*N; i++)
    // {
    //     cout << grid[i] << ' ';
    //     if(i % N == N-1) cout << '\n';
    // }

    cout << binary_search(0, INF) << '\n';
}

Subtask #1

53.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	372 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Runtime error	342 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Runtime error	806 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Incorrect	1 ms	620 KB	Output isn't correct
14	Correct	2 ms	876 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	492 KB	Output is correct
20	Correct	1 ms	492 KB	Output is correct
21	Correct	1 ms	492 KB	Output is correct
22	Correct	1 ms	492 KB	Output is correct
23	Correct	1 ms	640 KB	Output is correct
24	Correct	1 ms	620 KB	Output is correct
25	Correct	1 ms	876 KB	Output is correct
26	Correct	1 ms	876 KB	Output is correct
27	Correct	2 ms	876 KB	Output is correct
28	Correct	2 ms	876 KB	Output is correct
29	Correct	2 ms	1132 KB	Output is correct
30	Correct	3 ms	1004 KB	Output is correct
31	Correct	2 ms	1132 KB	Output is correct
32	Correct	2 ms	1132 KB	Output is correct
33	Correct	26 ms	16748 KB	Output is correct
34	Correct	28 ms	16748 KB	Output is correct
35	Correct	183 ms	16704 KB	Output is correct
36	Correct	31 ms	21740 KB	Output is correct
37	Correct	32 ms	21740 KB	Output is correct
38	Correct	244 ms	21740 KB	Output is correct
39	Correct	48 ms	27372 KB	Output is correct
40	Correct	45 ms	26476 KB	Output is correct
41	Correct	308 ms	27372 KB	Output is correct
42	Correct	51 ms	34028 KB	Output is correct
43	Correct	62 ms	34028 KB	Output is correct
44	Correct	411 ms	34028 KB	Output is correct
45	Correct	67 ms	40940 KB	Output is correct
46	Correct	65 ms	40940 KB	Output is correct
47	Correct	476 ms	40940 KB	Output is correct
48	Correct	73 ms	48748 KB	Output is correct
49	Correct	80 ms	48628 KB	Output is correct
50	Correct	571 ms	48876 KB	Output is correct
51	Correct	85 ms	57068 KB	Output is correct
52	Correct	85 ms	57068 KB	Output is correct
53	Correct	682 ms	57208 KB	Output is correct
54	Runtime error	112 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
55	Runtime error	111 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
56	Correct	798 ms	65536 KB	Output is correct
57	Runtime error	106 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
58	Runtime error	123 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
59	Runtime error	740 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Runtime error	120 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
61	Runtime error	120 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
62	Runtime error	688 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Runtime error	193 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
64	Runtime error	587 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
65	Runtime error	314 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
66	Runtime error	246 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
67	Runtime error	217 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
68	Runtime error	162 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
69	Runtime error	170 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
70	Runtime error	142 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
71	Runtime error	131 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
72	Runtime error	142 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
73	Runtime error	160 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	305 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	244 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	231 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	273 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	240 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	318 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	233 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	259 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	246 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	259 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	368 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	247 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	254 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	291 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	289 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	421 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	321 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	335 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	294 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)