Submission #338586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338586	2020-12-23T13:09:56 Z	blue	Mecho (IOI09_mecho)	C++11	56 / 100	807 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 = 1e9;

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

56.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 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	383 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	Incorrect	2 ms	748 KB	Output isn't correct
13	Incorrect	2 ms	620 KB	Output isn't correct
14	Correct	2 ms	748 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	620 KB	Output is correct
24	Correct	2 ms	620 KB	Output is correct
25	Correct	2 ms	748 KB	Output is correct
26	Correct	1 ms	748 KB	Output is correct
27	Correct	1 ms	876 KB	Output is correct
28	Correct	1 ms	876 KB	Output is correct
29	Correct	2 ms	1004 KB	Output is correct
30	Correct	2 ms	1024 KB	Output is correct
31	Correct	2 ms	1004 KB	Output is correct
32	Correct	2 ms	1004 KB	Output is correct
33	Correct	95 ms	16236 KB	Output is correct
34	Correct	28 ms	16256 KB	Output is correct
35	Correct	181 ms	16236 KB	Output is correct
36	Correct	31 ms	21100 KB	Output is correct
37	Correct	31 ms	21244 KB	Output is correct
38	Correct	249 ms	21228 KB	Output is correct
39	Correct	41 ms	26476 KB	Output is correct
40	Correct	49 ms	25836 KB	Output is correct
41	Correct	316 ms	26604 KB	Output is correct
42	Correct	50 ms	33004 KB	Output is correct
43	Correct	61 ms	33004 KB	Output is correct
44	Correct	421 ms	32984 KB	Output is correct
45	Correct	62 ms	39752 KB	Output is correct
46	Correct	63 ms	39788 KB	Output is correct
47	Correct	537 ms	39788 KB	Output is correct
48	Correct	74 ms	47212 KB	Output is correct
49	Correct	83 ms	47084 KB	Output is correct
50	Correct	574 ms	46828 KB	Output is correct
51	Correct	84 ms	55276 KB	Output is correct
52	Correct	85 ms	55276 KB	Output is correct
53	Correct	675 ms	55020 KB	Output is correct
54	Correct	103 ms	64108 KB	Output is correct
55	Correct	104 ms	64108 KB	Output is correct
56	Correct	807 ms	64348 KB	Output is correct
57	Runtime error	114 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
58	Runtime error	126 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
59	Runtime error	781 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Runtime error	119 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
61	Runtime error	120 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
62	Runtime error	742 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Runtime error	214 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
64	Runtime error	612 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
65	Runtime error	340 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
66	Runtime error	262 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
67	Runtime error	245 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
68	Runtime error	177 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
69	Runtime error	168 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
70	Runtime error	148 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
71	Runtime error	146 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
72	Runtime error	147 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
73	Runtime error	158 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	323 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	243 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	291 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	265 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	304 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	228 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	241 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	267 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	267 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	380 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	293 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	273 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	334 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	292 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	436 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	338 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	357 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	308 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)