Submission #255227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255227	2020-07-31T15:22:18 Z	DavidDamian	Mecho (IOI09_mecho)	C++11	21 / 100	1000 ms	6784 KB

mecho

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int i,j;
    node(){}
    node(int i,int j) : i(i),j(j){}
};
int n,s;
char board[605][605];
int bee[605][605];
int d[605][605];
int color[605][605];
int fuel[605][605];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<node> Q;
node start,finish;
void bfsBee()
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            bee[i][j]=INT_MAX;
            if(board[i][j]=='H'){
                Q.push(node(i,j));
                bee[i][j]=0;
                color[i][j]=-1;
            }
        }
    }
    while(Q.size()){
        node u=Q.front();Q.pop();
        for(int mov=0;mov<4;mov++){
            int i=u.i+dx[mov];
            int j=u.j+dy[mov];
            if(i<1 || i>n) continue;
            if(j<1 || j>n) continue;
            if(board[i][j]=='T' || board[i][j]=='D') continue;
            if(color[i][j]==0){
                color[i][j]=-1;
                Q.push(node(i,j));
                bee[i][j]=bee[u.i][u.j]+1;
            }
        }
    }
}
void bfsMecho(int init_d)
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[i][j]=INT_MAX;
        }
    }
    if(bee[start.i][start.j]<=init_d-1) return;
    d[start.i][start.j]=init_d-1;
    fuel[start.i][start.j]=0;
    color[start.i][start.j]=init_d;
    Q.push(start);
    while(Q.size()){
        node u=Q.front();Q.pop();
        for(int mov=0;mov<4;mov++){
            int i=u.i+dx[mov];
            int j=u.j+dy[mov];
            if(i<1 || i>n) continue;
            if(j<1 || j>n) continue;
            if(board[i][j]=='T') continue;
            if(color[i][j]!=init_d){
                d[i][j]=(fuel[u.i][u.j]>0)? d[u.i][u.j] : d[u.i][u.j]+1;
                if(bee[i][j]<=d[i][j]) continue;
                fuel[i][j]=(fuel[u.i][u.j]>0)? fuel[u.i][u.j]-1 : s-1;
                color[i][j]=init_d;
                Q.push(node(i,j));
            }
        }
    }
}
bool valid(int k)
{
    bfsMecho(k);
    return d[finish.i][finish.j]!=INT_MAX;
}
int binarySearch()
{
    int k=0;
    for(int b=1000;b>=1;b/=2){
        while(valid(k+b)) k+=b;
    }
    return (k==0)? -1 : k;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>board[i][j];
            if(board[i][j]=='M') start={i,j};
            if(board[i][j]=='D') finish={i,j};
        }
    }
    bfsBee();
    int maximum=binarySearch();
    cout<<maximum<<'\n';
    return 0;
}

Subtask #1

21.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Incorrect	1 ms	384 KB	Output isn't correct
3	Incorrect	1 ms	384 KB	Output isn't correct
4	Incorrect	0 ms	384 KB	Output isn't correct
5	Incorrect	1 ms	384 KB	Output isn't correct
6	Correct	1 ms	512 KB	Output is correct
7	Runtime error	9 ms	1920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	1 ms	512 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	0 ms	512 KB	Output is correct
11	Correct	0 ms	512 KB	Output is correct
12	Incorrect	1 ms	1024 KB	Output isn't correct
13	Incorrect	1 ms	768 KB	Output isn't correct
14	Correct	1 ms	896 KB	Output is correct
15	Incorrect	1 ms	512 KB	Output isn't correct
16	Correct	1 ms	512 KB	Output is correct
17	Incorrect	1 ms	512 KB	Output isn't correct
18	Correct	1 ms	640 KB	Output is correct
19	Incorrect	1 ms	640 KB	Output isn't correct
20	Correct	1 ms	640 KB	Output is correct
21	Incorrect	1 ms	640 KB	Output isn't correct
22	Correct	1 ms	640 KB	Output is correct
23	Incorrect	1 ms	768 KB	Output isn't correct
24	Correct	1 ms	768 KB	Output is correct
25	Incorrect	1 ms	896 KB	Output isn't correct
26	Correct	1 ms	896 KB	Output is correct
27	Incorrect	1 ms	896 KB	Output isn't correct
28	Correct	1 ms	1024 KB	Output is correct
29	Incorrect	1 ms	896 KB	Output isn't correct
30	Correct	1 ms	896 KB	Output is correct
31	Incorrect	1 ms	1024 KB	Output isn't correct
32	Correct	1 ms	1024 KB	Output is correct
33	Incorrect	32 ms	3632 KB	Output isn't correct
34	Correct	26 ms	3968 KB	Output is correct
35	Correct	29 ms	3968 KB	Output is correct
36	Incorrect	56 ms	4096 KB	Output isn't correct
37	Correct	43 ms	4480 KB	Output is correct
38	Correct	46 ms	4480 KB	Output is correct
39	Incorrect	104 ms	4608 KB	Output isn't correct
40	Correct	73 ms	5112 KB	Output is correct
41	Correct	71 ms	5240 KB	Output is correct
42	Incorrect	134 ms	5240 KB	Output isn't correct
43	Correct	98 ms	5664 KB	Output is correct
44	Correct	61 ms	5724 KB	Output is correct
45	Incorrect	171 ms	5504 KB	Output isn't correct
46	Correct	131 ms	6144 KB	Output is correct
47	Correct	87 ms	6264 KB	Output is correct
48	Incorrect	240 ms	6016 KB	Output isn't correct
49	Correct	188 ms	6776 KB	Output is correct
50	Correct	97 ms	6784 KB	Output is correct
51	Execution timed out	1086 ms	3968 KB	Time limit exceeded
52	Execution timed out	1075 ms	5376 KB	Time limit exceeded
53	Execution timed out	1094 ms	5248 KB	Time limit exceeded
54	Execution timed out	1095 ms	3968 KB	Time limit exceeded
55	Execution timed out	1090 ms	5376 KB	Time limit exceeded
56	Execution timed out	1099 ms	5376 KB	Time limit exceeded
57	Execution timed out	1089 ms	4096 KB	Time limit exceeded
58	Execution timed out	1095 ms	5504 KB	Time limit exceeded
59	Execution timed out	1095 ms	5376 KB	Time limit exceeded
60	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	9 ms	1824 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	10 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	8 ms	1856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	12 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	10 ms	1920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	12 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	12 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	9 ms	1920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	12 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	8 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	12 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	9 ms	1792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	10 ms	1920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)