Submission #244264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
244264	2020-07-03T12:41:30 Z	JovanK26	Mecho (IOI09_mecho)	C++14	18 / 100	337 ms	65540 KB

mecho

#include <bits/stdc++.h>

using namespace std;
int n,s;
bool is[801][801];
int tim[801][801];
bool vis[801][801];
struct field
{
    int x,y;
};
vector<field> hives;
field start;
field home;
bool check(int m)
{
     bool visited[801][801];
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<n;j++)
         {
             visited[i][j]=0;
         }
     }
     if(m>=tim[start.x][start.y])return 0;
     queue<pair<field,int> > q;
     q.push(make_pair(start,0));
     while(!q.empty())
    {
        auto x=q.front();
        q.pop();
        field cur=x.first;
        if(cur.x==home.x && cur.y==home.y)return 1;
        int d=x.second;
        visited[cur.x][cur.y]=1;
        if(cur.x+1<n && !visited[cur.x+1][cur.y] && is[cur.x+1][cur.y] && m+d/s<tim[cur.x+1][cur.y])
        {
            cur.x++;
            q.push(make_pair(cur,d+1));
            cur.x--;
        }
        if(cur.x-1>=0 && !visited[cur.x-1][cur.y] && is[cur.x-1][cur.y] && m+d/s<tim[cur.x-1][cur.y])
        {
            cur.x--;
            q.push(make_pair(cur,d+1));
            cur.x++;
        }
        if(cur.y+1<n && !visited[cur.x][cur.y+1] && is[cur.x][cur.y+1] && m+d/s<tim[cur.x][cur.y+1])
        {
            cur.y++;
            q.push(make_pair(cur,d+1));
            cur.y--;
        }
        if(cur.y-1>=0 && !visited[cur.x][cur.y-1] && is[cur.x][cur.y-1] && m+d/s<tim[cur.x][cur.y-1])
        {
            cur.y--;
            q.push(make_pair(cur,d+1));
            cur.y++;
        }
    }
    return 0;
}
int main()
{

    cin >> n >> s;
    char c;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
           cin >> c;
           if(c=='T')
           {
               is[i][j]=0;
           }
           else if(c=='M')
           {
               is[i][j]=1;
               start.x=i;
               start.y=j;
           }
           else if(c=='D')
           {
               is[i][j]=1;
               home.x=i;
               home.y=j;
           }
           else if(c=='H')
           {
               is[i][j]=1;
               field temp;
               temp.x=i;
               temp.y=j;
               hives.push_back(temp);
           }
           else
           {
               is[i][j]=1;
           }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            tim[i][j]=1000000;
        }
    }
    queue<pair<field,int> > q;
    for(int i=0;i<hives.size();i++)
    {
        q.push(make_pair(hives[i],0));
        vis[hives[i].x][hives[i].y]=1;
    }
    while(!q.empty())
    {
        auto x=q.front();
        q.pop();
        field cur=x.first;
        int d=x.second;
        //if(vis[cur.x][cur.y])continue;
        vis[cur.x][cur.y]=1;
        tim[cur.x][cur.y]=min(tim[cur.x][cur.y],d);
        if(cur.x+1<n && !vis[cur.x+1][cur.y] && is[cur.x+1][cur.y])
        {
            cur.x++;
            q.push(make_pair(cur,d+1));
            cur.x--;
        }
        if(cur.x-1>=0 && !vis[cur.x-1][cur.y] && is[cur.x-1][cur.y])
        {
            cur.x--;
            q.push(make_pair(cur,d+1));
            cur.x++;
        }
        if(cur.y+1<n && !vis[cur.x][cur.y+1] && is[cur.x][cur.y+1])
        {
            cur.y++;
            q.push(make_pair(cur,d+1));
            cur.y--;
        }
        if(cur.y-1>=0 && !vis[cur.x][cur.y-1] && is[cur.x][cur.y-1])
        {
            cur.y--;
            q.push(make_pair(cur,d+1));
            cur.y++;
        }
    }
    tim[home.x][home.y]=1000000;
    int l=0;
    int r=1000000;
    int m;
    int rez=1000000000;
    while(l<r)
    {
        m=(l+r)/2;
        if(check(m))
        {
            l=m+1;
            rez=m;
        }
        else
        {
            r=m;
        }
    }
    if(rez==1000000000)rez=-1;
    cout << rez;
    return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<hives.size();i++)
                 ~^~~~~~~~~~~~~

Subtask #1

18.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	384 KB	Output isn't correct
2	Incorrect	5 ms	384 KB	Output isn't correct
3	Incorrect	5 ms	384 KB	Output isn't correct
4	Incorrect	4 ms	384 KB	Output isn't correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Runtime error	231 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Incorrect	5 ms	384 KB	Output isn't correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Incorrect	5 ms	640 KB	Output isn't correct
13	Runtime error	267 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	337 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Incorrect	5 ms	384 KB	Output isn't correct
16	Correct	5 ms	384 KB	Output is correct
17	Incorrect	5 ms	512 KB	Output isn't correct
18	Correct	5 ms	512 KB	Output is correct
19	Incorrect	5 ms	512 KB	Output isn't correct
20	Correct	5 ms	512 KB	Output is correct
21	Incorrect	5 ms	512 KB	Output isn't correct
22	Correct	5 ms	512 KB	Output is correct
23	Incorrect	5 ms	640 KB	Output isn't correct
24	Correct	5 ms	640 KB	Output is correct
25	Incorrect	5 ms	640 KB	Output isn't correct
26	Correct	5 ms	640 KB	Output is correct
27	Incorrect	5 ms	640 KB	Output isn't correct
28	Correct	5 ms	640 KB	Output is correct
29	Incorrect	5 ms	768 KB	Output isn't correct
30	Correct	5 ms	768 KB	Output is correct
31	Incorrect	6 ms	768 KB	Output isn't correct
32	Correct	6 ms	768 KB	Output is correct
33	Incorrect	19 ms	2304 KB	Output isn't correct
34	Correct	18 ms	2432 KB	Output is correct
35	Runtime error	187 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Incorrect	23 ms	2688 KB	Output isn't correct
37	Correct	22 ms	2688 KB	Output is correct
38	Runtime error	186 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Incorrect	28 ms	2944 KB	Output isn't correct
40	Correct	27 ms	2936 KB	Output is correct
41	Runtime error	189 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Incorrect	34 ms	3320 KB	Output isn't correct
43	Correct	32 ms	3328 KB	Output is correct
44	Runtime error	191 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Incorrect	39 ms	3584 KB	Output isn't correct
46	Correct	40 ms	3704 KB	Output is correct
47	Runtime error	201 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	45 ms	3960 KB	Output isn't correct
49	Correct	44 ms	3960 KB	Output is correct
50	Runtime error	202 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Incorrect	52 ms	4344 KB	Output isn't correct
52	Correct	51 ms	4348 KB	Output is correct
53	Runtime error	210 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Incorrect	61 ms	4600 KB	Output isn't correct
55	Correct	57 ms	4728 KB	Output is correct
56	Runtime error	210 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Incorrect	66 ms	4984 KB	Output isn't correct
58	Correct	65 ms	4984 KB	Output is correct
59	Runtime error	219 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Incorrect	76 ms	5368 KB	Output isn't correct
61	Correct	72 ms	5368 KB	Output is correct
62	Runtime error	225 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Correct	150 ms	5368 KB	Output is correct
64	Correct	188 ms	5368 KB	Output is correct
65	Correct	187 ms	5368 KB	Output is correct
66	Incorrect	176 ms	5496 KB	Output isn't correct
67	Correct	153 ms	5372 KB	Output is correct
68	Correct	107 ms	5368 KB	Output is correct
69	Correct	101 ms	5368 KB	Output is correct
70	Correct	94 ms	5368 KB	Output is correct
71	Correct	90 ms	5496 KB	Output is correct
72	Correct	89 ms	5368 KB	Output is correct
73	Runtime error	309 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	308 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	310 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	309 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	305 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	282 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	283 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	278 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	283 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	279 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	260 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	257 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	256 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	256 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	243 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	244 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	245 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	236 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	243 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)