oj.uz

Submission #313756

# Submission time Handle Problem Language Result Execution time Memory
313756 2020-10-16T23:45:53 Z Massiosare Mecho (IOI09_mecho) C++14
23 / 100
 274 ms 6392 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];
bool 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'){
            if(valores[temp.fil][temp.col]<=temp.nivel){
                return 0;
            }
            return 1;
        }
        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;
            }
        }
        while(!q2.empty()){
            q2.pop();
        }
        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
23.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Incorrect 222 ms 5200 KB Output isn't correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Incorrect 0 ms 384 KB Output isn't correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Incorrect 1 ms 640 KB Output isn't correct
13 Correct 1 ms 640 KB Output is correct
14 Incorrect 1 ms 640 KB Output isn't correct
15 Incorrect 1 ms 384 KB Output isn't correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Incorrect 1 ms 384 KB Output isn't correct
18 Incorrect 1 ms 384 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 512 KB Output isn't correct
22 Incorrect 1 ms 512 KB Output isn't correct
23 Incorrect 1 ms 512 KB Output isn't correct
24 Incorrect 1 ms 512 KB Output isn't correct
25 Incorrect 1 ms 640 KB Output isn't correct
26 Incorrect 1 ms 640 KB Output isn't correct
27 Incorrect 1 ms 640 KB Output isn't correct
28 Incorrect 1 ms 640 KB Output isn't correct
29 Incorrect 1 ms 640 KB Output isn't correct
30 Incorrect 1 ms 640 KB Output isn't correct
31 Incorrect 1 ms 640 KB Output isn't correct
32 Incorrect 1 ms 640 KB Output isn't correct
33 Incorrect 18 ms 2048 KB Output isn't correct
34 Incorrect 18 ms 2048 KB Output isn't correct
35 Correct 48 ms 2048 KB Output is correct
36 Incorrect 23 ms 2304 KB Output isn't correct
37 Incorrect 23 ms 2176 KB Output isn't correct
38 Correct 66 ms 2316 KB Output is correct
39 Incorrect 28 ms 2424 KB Output isn't correct
40 Incorrect 29 ms 2432 KB Output isn't correct
41 Correct 85 ms 2560 KB Output is correct
42 Incorrect 35 ms 2680 KB Output isn't correct
43 Incorrect 35 ms 2680 KB Output isn't correct
44 Correct 100 ms 2764 KB Output is correct
45 Incorrect 42 ms 3064 KB Output isn't correct
46 Incorrect 43 ms 2936 KB Output isn't correct
47 Correct 126 ms 2944 KB Output is correct
48 Incorrect 50 ms 3192 KB Output isn't correct
49 Incorrect 49 ms 3192 KB Output isn't correct
50 Correct 150 ms 3192 KB Output is correct
51 Incorrect 58 ms 3576 KB Output isn't correct
52 Incorrect 60 ms 3576 KB Output isn't correct
53 Correct 177 ms 3448 KB Output is correct
54 Incorrect 69 ms 3704 KB Output isn't correct
55 Incorrect 67 ms 3704 KB Output isn't correct
56 Correct 206 ms 3832 KB Output is correct
57 Incorrect 75 ms 3960 KB Output isn't correct
58 Incorrect 77 ms 3916 KB Output isn't correct
59 Correct 238 ms 3960 KB Output is correct
60 Incorrect 87 ms 4216 KB Output isn't correct
61 Incorrect 87 ms 4216 KB Output isn't correct
62 Correct 274 ms 4216 KB Output is correct
63 Correct 91 ms 4344 KB Output is correct
64 Incorrect 268 ms 4216 KB Output isn't correct
65 Incorrect 220 ms 4216 KB Output isn't correct
66 Incorrect 87 ms 4220 KB Output isn't correct
67 Incorrect 120 ms 4216 KB Output isn't correct
68 Correct 111 ms 5496 KB Output is correct
69 Incorrect 119 ms 5368 KB Output isn't correct
70 Incorrect 107 ms 5368 KB Output isn't correct
71 Incorrect 102 ms 5368 KB Output isn't correct
72 Incorrect 99 ms 5368 KB Output isn't correct
73 Correct 109 ms 6392 KB Output is correct
74 Correct 172 ms 6264 KB Output is correct
75 Correct 175 ms 6264 KB Output is correct
76 Correct 170 ms 6392 KB Output is correct
77 Correct 175 ms 6296 KB Output is correct
78 Incorrect 185 ms 5708 KB Output isn't correct
79 Correct 148 ms 5708 KB Output is correct
80 Correct 162 ms 5832 KB Output is correct
81 Correct 188 ms 5704 KB Output is correct
82 Correct 163 ms 5836 KB Output is correct
83 Correct 192 ms 5796 KB Output is correct
84 Correct 173 ms 5660 KB Output is correct
85 Correct 178 ms 5792 KB Output is correct
86 Correct 196 ms 5792 KB Output is correct
87 Correct 179 ms 5792 KB Output is correct
88 Correct 220 ms 4964 KB Output is correct
89 Correct 196 ms 4972 KB Output is correct
90 Correct 210 ms 4968 KB Output is correct
91 Correct 211 ms 5092 KB Output is correct
92 Correct 208 ms 5092 KB Output is correct