oj.uz

Submission #313753

# Submission time Handle Problem Language Result Execution time Memory
313753 2020-10-16T23:32:48 Z Massiosare Mecho (IOI09_mecho) C++14
8 / 100
 252 ms 8952 KB 
#include <iostream>
#include <queue>

#define MAX 805

using namespace std;

struct coords{
    int fil;
    int col;
    int nivel;
    int temporal;
};

int best;
int maxpro;
coords pro,start;
int n,steps;
char mat[MAX][MAX];
int visitados[MAX][MAX];
int valores[MAX][MAX];
queue <coords> q,q2;

void add(coords temp){
    coords temp2=temp;
    temp2.nivel++;
    //col+
    temp2.col++;
    q.push(temp2);
    temp2.col--;
    //fil+
    temp2.fil++;
    q.push(temp2);
    temp2.fil--;
    //col-
    temp2.col--;
    q.push(temp2);
    temp2.col++;
    //fil-
    temp2.fil--;
    q.push(temp2);
    temp2.fil++;
    return;
}

void add2(coords temp){
    coords temp2=temp;
    temp2.temporal++;
    if(temp2.temporal%steps==0){
        temp2.nivel++;
    }
    //col+
    temp2.col++;
    q2.push(temp2);
    temp2.col--;
    //fil+
    temp2.fil++;
    q2.push(temp2);
    temp2.fil--;
    //col-
    temp2.col--;
    q2.push(temp2);
    temp2.col++;
    //fil-
    temp2.fil--;
    q2.push(temp2);
    temp2.fil++;
    return;
}

bool busca2(){
    while(!q2.empty()){
        coords temp=q2.front();
        q2.pop();
        if(temp.col<1||temp.col>n||temp.fil>n||temp.fil<1){
            continue;
        }
        if(visitados[temp.fil][temp.col]==1||mat[temp.fil][temp.col]=='T'){
            continue;
        }
        else {
            visitados[temp.fil][temp.col]=1;
        }
        if(valores[temp.fil][temp.col]<=temp.nivel){
            continue;
        }
        if(mat[temp.fil][temp.col]=='D'){
            return 1;
            if(valores[temp.fil][temp.col]<=temp.nivel){
                return 0;
            }
        }
        add2(temp);
    }
    return 0;
}

void binaria(int ini,int fin){
    while(ini<=fin){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                visitados[i][j]=0;
            }
        }
        int mid=(ini+fin)/2;
        start.nivel=mid;
        q2.push(start);
        bool x=busca2();
        if(x==1){
            best=mid;
            ini=mid+1;
        }
        else {
            fin=mid-1;
        }
    }
    cout << best;
}

void busca(){
    while(!q.empty()){
        coords temp=q.front();
        q.pop();
        if(temp.col<1||temp.col>n||temp.fil>n||temp.fil<1){
            continue;
        }
        if(visitados[temp.fil][temp.col]==0){
            valores[temp.fil][temp.col]=temp.nivel;
            visitados[temp.fil][temp.col]=1;
        }
        else {
            continue;
        }
        if(mat[temp.fil][temp.col]=='M'){
            maxpro=valores[temp.fil][temp.col];
        }
        add(temp);
    }
    return;
}

int main()
{
    cin >> n >> steps;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
            if(mat[i][j]=='H'){
                pro.fil=i;
                pro.col=j;
                q.push(pro);
            }
            if(mat[i][j]=='M'){
                start.fil=i;
                start.col=j;
                start.nivel=0;
            }
        }
    }
    busca();
    binaria(1,maxpro);
    return 0;
}

Subtask #1
8.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Incorrect 161 ms 7632 KB Output isn't correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Incorrect 1 ms 768 KB Output isn't correct
13 Correct 1 ms 768 KB Output is correct
14 Incorrect 2 ms 768 KB Output isn't correct
15 Incorrect 1 ms 512 KB Output isn't correct
16 Incorrect 1 ms 512 KB Output isn't correct
17 Incorrect 1 ms 512 KB Output isn't correct
18 Incorrect 1 ms 512 KB Output isn't correct
19 Incorrect 1 ms 512 KB Output isn't correct
20 Incorrect 1 ms 512 KB Output isn't correct
21 Incorrect 1 ms 640 KB Output isn't correct
22 Incorrect 1 ms 640 KB Output isn't correct
23 Incorrect 1 ms 640 KB Output isn't correct
24 Incorrect 1 ms 640 KB Output isn't correct
25 Incorrect 1 ms 768 KB Output isn't correct
26 Incorrect 1 ms 896 KB Output isn't correct
27 Incorrect 1 ms 768 KB Output isn't correct
28 Incorrect 2 ms 768 KB Output isn't correct
29 Incorrect 2 ms 896 KB Output isn't correct
30 Incorrect 2 ms 896 KB Output isn't correct
31 Incorrect 2 ms 896 KB Output isn't correct
32 Incorrect 2 ms 896 KB Output isn't correct
33 Incorrect 19 ms 2944 KB Output isn't correct
34 Incorrect 19 ms 2944 KB Output isn't correct
35 Correct 44 ms 2944 KB Output is correct
36 Incorrect 24 ms 3328 KB Output isn't correct
37 Incorrect 25 ms 3448 KB Output isn't correct
38 Incorrect 57 ms 3448 KB Output isn't correct
39 Incorrect 31 ms 3712 KB Output isn't correct
40 Incorrect 31 ms 3832 KB Output isn't correct
41 Incorrect 72 ms 3832 KB Output isn't correct
42 Incorrect 37 ms 4220 KB Output isn't correct
43 Incorrect 37 ms 4088 KB Output isn't correct
44 Incorrect 92 ms 4224 KB Output isn't correct
45 Incorrect 45 ms 4600 KB Output isn't correct
46 Incorrect 47 ms 4600 KB Output isn't correct
47 Incorrect 107 ms 4600 KB Output isn't correct
48 Incorrect 54 ms 5112 KB Output isn't correct
49 Incorrect 55 ms 5028 KB Output isn't correct
50 Incorrect 130 ms 5060 KB Output isn't correct
51 Incorrect 64 ms 5368 KB Output isn't correct
52 Incorrect 61 ms 5432 KB Output isn't correct
53 Correct 166 ms 5496 KB Output is correct
54 Incorrect 71 ms 5752 KB Output isn't correct
55 Incorrect 71 ms 5808 KB Output isn't correct
56 Correct 191 ms 5880 KB Output is correct
57 Incorrect 86 ms 6264 KB Output isn't correct
58 Incorrect 82 ms 6264 KB Output isn't correct
59 Correct 225 ms 6392 KB Output is correct
60 Incorrect 95 ms 6648 KB Output isn't correct
61 Incorrect 92 ms 6648 KB Output isn't correct
62 Incorrect 252 ms 6776 KB Output isn't correct
63 Correct 97 ms 6776 KB Output is correct
64 Incorrect 115 ms 6648 KB Output isn't correct
65 Incorrect 229 ms 6648 KB Output isn't correct
66 Incorrect 95 ms 6648 KB Output isn't correct
67 Incorrect 124 ms 6648 KB Output isn't correct
68 Correct 127 ms 8056 KB Output is correct
69 Incorrect 129 ms 7928 KB Output isn't correct
70 Incorrect 117 ms 7928 KB Output isn't correct
71 Incorrect 116 ms 7928 KB Output isn't correct
72 Incorrect 120 ms 7928 KB Output isn't correct
73 Incorrect 121 ms 8952 KB Output isn't correct
74 Incorrect 137 ms 8836 KB Output isn't correct
75 Incorrect 129 ms 8824 KB Output isn't correct
76 Incorrect 132 ms 8852 KB Output isn't correct
77 Incorrect 135 ms 8824 KB Output isn't correct
78 Incorrect 206 ms 8268 KB Output isn't correct
79 Incorrect 123 ms 8140 KB Output isn't correct
80 Incorrect 129 ms 8136 KB Output isn't correct
81 Incorrect 142 ms 8136 KB Output isn't correct
82 Incorrect 120 ms 8188 KB Output isn't correct
83 Correct 203 ms 8228 KB Output is correct
84 Incorrect 136 ms 8220 KB Output isn't correct
85 Incorrect 125 ms 8352 KB Output isn't correct
86 Incorrect 155 ms 8224 KB Output isn't correct
87 Incorrect 133 ms 8224 KB Output isn't correct
88 Correct 200 ms 7524 KB Output is correct
89 Incorrect 139 ms 7528 KB Output isn't correct
90 Incorrect 161 ms 7528 KB Output isn't correct
91 Incorrect 145 ms 7524 KB Output isn't correct
92 Incorrect 172 ms 7524 KB Output isn't correct