Submission #338583

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338583	2020-12-23T13:06:52 Z	blue	Mecho (IOI09_mecho)	C++11	44 / 100	485 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
*/
long long N, S;
long long grid[800*800]; //the number of minutes before this location cannot be occupied anymore.
long long mecho;
long long home;
//LOOKS GOOD

long long INF = 2e9;

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

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

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


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

        vector<long long> 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(long long 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(long long 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<long long> visit(N*N, 0);

    queue<long long> tbv;

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

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

        vector<long long> 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(long long v: edge)
        {
            if(visit[v]) continue;
            if(grid[v] > grid[u] + S)
            {
                grid[v] = grid[u] + S;
                tbv.push(v);
            }
        }
    }

    grid[home] = INF;

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

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

Subtask #1

44.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 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	161 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	1260 KB	Output isn't correct
13	Incorrect	2 ms	1004 KB	Output isn't correct
14	Correct	3 ms	1260 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Correct	1 ms	492 KB	Output is correct
18	Correct	1 ms	492 KB	Output is correct
19	Correct	1 ms	620 KB	Output is correct
20	Correct	1 ms	620 KB	Output is correct
21	Correct	1 ms	748 KB	Output is correct
22	Correct	1 ms	748 KB	Output is correct
23	Correct	1 ms	1004 KB	Output is correct
24	Correct	2 ms	1004 KB	Output is correct
25	Correct	2 ms	1260 KB	Output is correct
26	Correct	2 ms	1260 KB	Output is correct
27	Correct	2 ms	1516 KB	Output is correct
28	Correct	2 ms	1516 KB	Output is correct
29	Correct	2 ms	1644 KB	Output is correct
30	Correct	3 ms	1644 KB	Output is correct
31	Correct	3 ms	1900 KB	Output is correct
32	Correct	3 ms	1900 KB	Output is correct
33	Correct	35 ms	33132 KB	Output is correct
34	Correct	39 ms	33132 KB	Output is correct
35	Correct	230 ms	33260 KB	Output is correct
36	Correct	42 ms	43116 KB	Output is correct
37	Correct	42 ms	43116 KB	Output is correct
38	Correct	304 ms	43244 KB	Output is correct
39	Correct	54 ms	54508 KB	Output is correct
40	Correct	66 ms	52972 KB	Output is correct
41	Correct	371 ms	54636 KB	Output is correct
42	Runtime error	68 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
43	Runtime error	90 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
44	Runtime error	485 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Runtime error	76 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
46	Runtime error	81 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
47	Runtime error	426 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Runtime error	96 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
49	Runtime error	95 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
50	Runtime error	344 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Runtime error	115 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
52	Runtime error	96 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Runtime error	252 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Runtime error	108 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
55	Runtime error	125 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
56	Runtime error	168 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Runtime error	103 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
58	Runtime error	128 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
59	Runtime error	160 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Runtime error	116 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
61	Runtime error	116 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
62	Runtime error	152 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Runtime error	133 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
64	Runtime error	169 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
65	Runtime error	132 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
66	Runtime error	133 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
67	Runtime error	131 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
68	Runtime error	146 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
69	Runtime error	141 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
70	Runtime error	147 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
71	Runtime error	169 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
72	Runtime error	139 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
73	Runtime error	177 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	179 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	184 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	176 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	178 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	205 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	169 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	167 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	188 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	181 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	166 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	169 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	174 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	178 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	163 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	169 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	171 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	169 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	190 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	167 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)