oj.uz

Submission #335734

# Submission time Handle Problem Language Result Execution time Memory
335734 2020-12-13T19:33:36 Z DavidDamian Mecho (IOI09_mecho) C++11
4 / 100
 1000 ms 8888 KB 
#include <bits/stdc++.h>
using namespace std;
struct node{
    int i;
    int j;
    node(){}
    node(int I,int J){
        i=I;
        j=J;
    }
};
queue<node> Q;
char forest[805][805];
int bees[805][805];
int dist[805][805];
int energy[805][805];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,s;

void bfsBees(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            bees[i][j]=INT_MAX;
            if(forest[i][j]=='H'){
                Q.push(node(i,j));
                bees[i][j]=0;
            }
        }
    }
    while(!Q.empty()){
        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(forest[i][j]=='T' || forest[i][j]=='D') continue;
            if(bees[i][j]==INT_MAX){
                bees[i][j]=bees[u.i][u.j]+1;
                Q.push(node(i,j));
            }
        }
    }
}

node mecho;
node home;

bool bfsMecho(int init){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dist[i][j]=INT_MAX;
            energy[i][j]=0;
        }
    }
    dist[mecho.i][mecho.j]=init;
    energy[mecho.i][mecho.j]=0;
    Q.push(mecho);
    while(!Q.empty()){
        node u=Q.front();
        Q.pop();
        if(bees[u.i][u.j]==dist[u.i][u.j] && energy[u.i][u.j]==0) continue;
        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(forest[i][j]=='T') continue;
            if(dist[i][j]==INT_MAX){
                int change=(energy[u.i][u.j]>0)? 0 : 1;
                dist[i][j]=dist[u.i][u.j]+change;
                if(bees[i][j]<dist[i][j]) continue;
                energy[i][j]=(energy[u.i][u.j]>0)? energy[u.i][u.j]-1 : s-1;
                Q.push(node(i,j));
            }
        }
    }
    return dist[home.i][home.j]!=INT_MAX;
}

int binarySearch(){
    int k=-1;
    int L=0,R=3*n;
    while(L<R){
        int mid=(L+R)/2;
        if(bfsMecho(mid)){
            k=mid;
            L=mid;
        }
        else{
            R=mid-1;
        }
    }
    return k;
}

int binarySearch2(){
    int k=-1;
    for(int b=10000;b>=1;b/=2){
        while(bfsMecho(b+k)) k+=b;
    }
    return 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>>forest[i][j];
            if(forest[i][j]=='M'){
                mecho=node(i,j);
            }
            else if(forest[i][j]=='D'){
                home=node(i,j);
            }
        }
    }
    bfsBees();
    int ans=binarySearch();
    cout<<ans<<endl;
    return 0;
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 364 KB Time limit exceeded
2 Execution timed out 1098 ms 364 KB Time limit exceeded
3 Execution timed out 1094 ms 364 KB Time limit exceeded
4 Execution timed out 1052 ms 492 KB Time limit exceeded
5 Execution timed out 1054 ms 364 KB Time limit exceeded
6 Execution timed out 1097 ms 492 KB Time limit exceeded
7 Execution timed out 1079 ms 8684 KB Time limit exceeded
8 Correct 1 ms 492 KB Output is correct
9 Execution timed out 1099 ms 492 KB Time limit exceeded
10 Execution timed out 1075 ms 492 KB Time limit exceeded
11 Correct 1 ms 492 KB Output is correct
12 Execution timed out 1085 ms 1004 KB Time limit exceeded
13 Incorrect 1 ms 876 KB Output isn't correct
14 Correct 1 ms 1004 KB Output is correct
15 Execution timed out 1099 ms 492 KB Time limit exceeded
16 Execution timed out 1100 ms 492 KB Time limit exceeded
17 Execution timed out 1095 ms 620 KB Time limit exceeded
18 Execution timed out 1089 ms 620 KB Time limit exceeded
19 Execution timed out 1092 ms 620 KB Time limit exceeded
20 Execution timed out 1066 ms 748 KB Time limit exceeded
21 Execution timed out 1096 ms 748 KB Time limit exceeded
22 Execution timed out 1094 ms 748 KB Time limit exceeded
23 Execution timed out 1092 ms 876 KB Time limit exceeded
24 Execution timed out 1093 ms 876 KB Time limit exceeded
25 Execution timed out 1095 ms 1004 KB Time limit exceeded
26 Execution timed out 1089 ms 1004 KB Time limit exceeded
27 Execution timed out 1089 ms 1004 KB Time limit exceeded
28 Execution timed out 1085 ms 1004 KB Time limit exceeded
29 Execution timed out 1075 ms 1004 KB Time limit exceeded
30 Execution timed out 1090 ms 1132 KB Time limit exceeded
31 Execution timed out 1094 ms 1132 KB Time limit exceeded
32 Execution timed out 1087 ms 1132 KB Time limit exceeded
33 Execution timed out 1088 ms 3948 KB Time limit exceeded
34 Execution timed out 1104 ms 3948 KB Time limit exceeded
35 Correct 27 ms 3948 KB Output is correct
36 Execution timed out 1087 ms 4460 KB Time limit exceeded
37 Execution timed out 1089 ms 4460 KB Time limit exceeded
38 Execution timed out 1100 ms 4460 KB Time limit exceeded
39 Execution timed out 1099 ms 4972 KB Time limit exceeded
40 Execution timed out 1099 ms 4972 KB Time limit exceeded
41 Execution timed out 1099 ms 4972 KB Time limit exceeded
42 Execution timed out 1090 ms 5484 KB Time limit exceeded
43 Execution timed out 1088 ms 5484 KB Time limit exceeded
44 Execution timed out 1092 ms 5484 KB Time limit exceeded
45 Execution timed out 1058 ms 5996 KB Time limit exceeded
46 Execution timed out 1086 ms 5996 KB Time limit exceeded
47 Execution timed out 1079 ms 5996 KB Time limit exceeded
48 Execution timed out 1094 ms 6508 KB Time limit exceeded
49 Execution timed out 1092 ms 6508 KB Time limit exceeded
50 Execution timed out 1082 ms 6508 KB Time limit exceeded
51 Execution timed out 1050 ms 7020 KB Time limit exceeded
52 Execution timed out 1091 ms 7020 KB Time limit exceeded
53 Execution timed out 1082 ms 7020 KB Time limit exceeded
54 Execution timed out 1088 ms 7532 KB Time limit exceeded
55 Execution timed out 1092 ms 7532 KB Time limit exceeded
56 Correct 124 ms 7532 KB Output is correct
57 Execution timed out 1100 ms 8044 KB Time limit exceeded
58 Execution timed out 1093 ms 8044 KB Time limit exceeded
59 Correct 150 ms 8228 KB Output is correct
60 Execution timed out 1100 ms 8556 KB Time limit exceeded
61 Execution timed out 1097 ms 8556 KB Time limit exceeded
62 Execution timed out 1056 ms 8556 KB Time limit exceeded
63 Incorrect 110 ms 8684 KB Output isn't correct
64 Correct 217 ms 8556 KB Output is correct
65 Correct 183 ms 8684 KB Output is correct
66 Execution timed out 1095 ms 8556 KB Time limit exceeded
67 Correct 128 ms 8684 KB Output is correct
68 Incorrect 59 ms 8556 KB Output isn't correct
69 Correct 53 ms 8556 KB Output is correct
70 Execution timed out 1066 ms 8556 KB Time limit exceeded
71 Execution timed out 1086 ms 8556 KB Time limit exceeded
72 Correct 49 ms 8560 KB Output is correct
73 Execution timed out 1085 ms 8812 KB Time limit exceeded
74 Correct 115 ms 8888 KB Output is correct
75 Execution timed out 1090 ms 8812 KB Time limit exceeded
76 Execution timed out 1087 ms 8812 KB Time limit exceeded
77 Execution timed out 1079 ms 8812 KB Time limit exceeded
78 Correct 89 ms 8812 KB Output is correct
79 Execution timed out 1088 ms 8804 KB Time limit exceeded
80 Execution timed out 1085 ms 8808 KB Time limit exceeded
81 Correct 106 ms 8812 KB Output is correct
82 Execution timed out 1093 ms 8812 KB Time limit exceeded
83 Incorrect 98 ms 8812 KB Output isn't correct
84 Execution timed out 1093 ms 8812 KB Time limit exceeded
85 Execution timed out 1087 ms 8812 KB Time limit exceeded
86 Correct 100 ms 8812 KB Output is correct
87 Execution timed out 1079 ms 8812 KB Time limit exceeded
88 Incorrect 98 ms 8768 KB Output isn't correct
89 Execution timed out 1076 ms 8688 KB Time limit exceeded
90 Correct 110 ms 8684 KB Output is correct
91 Execution timed out 1093 ms 8684 KB Time limit exceeded
92 Execution timed out 1091 ms 8684 KB Time limit exceeded