oj.uz

Submission #643370

# Submission time Handle Problem Language Result Execution time Memory
643370 2022-09-21T22:28:30 Z AtinaR Mecho (IOI09_mecho) C++14
52 / 100
 188 ms 5068 KB 
#include <bits/stdc++.h>

using namespace std;
const int MAX=810;
const int INF=(1<<30);
int di[4]={0,0,-1,1};
int dj[4]={1,-1,0,0};
int n,s;
char mat[MAX][MAX];
int timebees[MAX][MAX];
bool visbees[MAX][MAX];
bool vis[MAX][MAX];
vector<pair<int,int> > hiveinitial;
vector<pair<int,int> > homeinitial;
int mi,mj;
bool validBees(int i, int j)
{
    if(i<0 || i>n || j<0 || j>n || mat[i][j]=='T'||mat[i][j]=='D'||visbees[i][j])return false;
    return true;
}
bool validBear(int i, int j)
{
    if(i<0 || i>n || j<0 || j>n || mat[i][j]!='G' || vis[i][j])return false;
    return true;
}
void bfsBees()
{
    queue<pair<int,int> > q;
    for(int i=0; i<hiveinitial.size(); i++)
    {
        int x=hiveinitial[i].first;
        int y=hiveinitial[i].second;
        q.push({x,y});
        visbees[x][y]=true;
        timebees[x][y]=0;
    }
    while(!q.empty())
    {
        pair<int,int> curr=q.front();
        q.pop();
        int x=curr.first;
        int y=curr.second;
        for(int k=0; k<4; k++)
        {
            int newi=x+di[k];
            int newj=y+dj[k];
            if(validBees(newi,newj))
            {
                q.push({newi,newj});
                timebees[newi][newj]=timebees[x][y]+1;
                visbees[newi][newj]=true;
            }
        }
    }
    return;
}
bool bearreached(int mechodis, int beedis)
{
    return mechodis/s<beedis;
}
bool canReach(int secs)
{
    queue<pair<int,int> > q;
    q.push({mi,mj});
    if(timebees[mi][mj]<=secs)
    {
        return false;
    }
    memset(vis,false,sizeof(vis));
    vis[mi][mj]=true;
    queue<int> steps;
    steps.push(0);
    while(!q.empty())
    {
        pair<int,int> curr=q.front();
        int x=curr.first;
        int y=curr.second;
        int currstep=steps.front();
        steps.pop();
        q.pop();
        for(int k=0; k<4; k++)
        {
            int newi=x+di[k];
            int newj=y+dj[k];
            if(mat[newi][newj]=='D')return true;
            if(validBear(newi,newj))
            {
                if(bearreached(currstep+1,timebees[newi][newj]-secs))
                {
                    q.push({newi,newj});
                    steps.push(currstep+1);
                    vis[newi][newj]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>mat[i][j];
            if(mat[i][j]=='H')
            {
                hiveinitial.push_back({i,j});
            }
            if(mat[i][j]=='M')
            {
                mi=i;
                mj=j;
            }
        }
    }
    bfsBees();
    int b=0;
    int e=n*n;
    while(b<=e)
    {
        int mid=(b+e)/2;
        if(canReach(mid))
        {
            b=mid+1;
        }
        else
        {
            e=mid-1;
        }
    }
    cout<<b-1<<endl;
    return 0;
}

Compilation message

mecho.cpp: In function 'void bfsBees()':
mecho.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0; i<hiveinitial.size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~~~

Subtask #1
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 100 ms 4884 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 1 ms 1108 KB Output is correct
14 Correct 1 ms 1236 KB Output is correct
15 Incorrect 1 ms 980 KB Output isn't correct
16 Incorrect 1 ms 980 KB Output isn't correct
17 Incorrect 1 ms 1108 KB Output isn't correct
18 Incorrect 1 ms 980 KB Output isn't correct
19 Incorrect 1 ms 1108 KB Output isn't correct
20 Incorrect 1 ms 1108 KB Output isn't correct
21 Incorrect 1 ms 1108 KB Output isn't correct
22 Incorrect 1 ms 1108 KB Output isn't correct
23 Incorrect 1 ms 1108 KB Output isn't correct
24 Incorrect 1 ms 1108 KB Output isn't correct
25 Incorrect 1 ms 1236 KB Output isn't correct
26 Incorrect 1 ms 1236 KB Output isn't correct
27 Incorrect 1 ms 1236 KB Output isn't correct
28 Incorrect 1 ms 1236 KB Output isn't correct
29 Incorrect 1 ms 1236 KB Output isn't correct
30 Incorrect 2 ms 1236 KB Output isn't correct
31 Incorrect 1 ms 1236 KB Output isn't correct
32 Incorrect 1 ms 1236 KB Output isn't correct
33 Incorrect 5 ms 2644 KB Output isn't correct
34 Incorrect 8 ms 2644 KB Output isn't correct
35 Correct 24 ms 2644 KB Output is correct
36 Incorrect 6 ms 2772 KB Output isn't correct
37 Incorrect 12 ms 2900 KB Output isn't correct
38 Correct 32 ms 2808 KB Output is correct
39 Incorrect 6 ms 3028 KB Output isn't correct
40 Incorrect 16 ms 3072 KB Output isn't correct
41 Correct 41 ms 3028 KB Output is correct
42 Incorrect 7 ms 3284 KB Output isn't correct
43 Incorrect 19 ms 3264 KB Output isn't correct
44 Correct 51 ms 3328 KB Output is correct
45 Incorrect 9 ms 3552 KB Output isn't correct
46 Incorrect 19 ms 3592 KB Output isn't correct
47 Correct 61 ms 3592 KB Output is correct
48 Incorrect 12 ms 3772 KB Output isn't correct
49 Incorrect 29 ms 3828 KB Output isn't correct
50 Correct 69 ms 3720 KB Output is correct
51 Incorrect 11 ms 4052 KB Output isn't correct
52 Incorrect 26 ms 4052 KB Output isn't correct
53 Correct 84 ms 4068 KB Output is correct
54 Incorrect 13 ms 4308 KB Output isn't correct
55 Incorrect 29 ms 4252 KB Output isn't correct
56 Correct 108 ms 4312 KB Output is correct
57 Incorrect 25 ms 4444 KB Output isn't correct
58 Incorrect 39 ms 4492 KB Output isn't correct
59 Correct 148 ms 4544 KB Output is correct
60 Incorrect 18 ms 4684 KB Output isn't correct
61 Incorrect 43 ms 4672 KB Output isn't correct
62 Correct 136 ms 4788 KB Output is correct
63 Incorrect 77 ms 4776 KB Output isn't correct
64 Incorrect 188 ms 4780 KB Output isn't correct
65 Incorrect 173 ms 4780 KB Output isn't correct
66 Incorrect 99 ms 4684 KB Output isn't correct
67 Correct 120 ms 4780 KB Output is correct
68 Correct 56 ms 4808 KB Output is correct
69 Correct 46 ms 4684 KB Output is correct
70 Incorrect 42 ms 4820 KB Output isn't correct
71 Incorrect 38 ms 4816 KB Output isn't correct
72 Incorrect 44 ms 4696 KB Output isn't correct
73 Correct 39 ms 5068 KB Output is correct
74 Correct 69 ms 5068 KB Output is correct
75 Correct 78 ms 5068 KB Output is correct
76 Correct 66 ms 5000 KB Output is correct
77 Correct 67 ms 5068 KB Output is correct
78 Correct 84 ms 5028 KB Output is correct
79 Correct 54 ms 5032 KB Output is correct
80 Correct 63 ms 5032 KB Output is correct
81 Correct 72 ms 4948 KB Output is correct
82 Correct 64 ms 4948 KB Output is correct
83 Correct 92 ms 5004 KB Output is correct
84 Correct 85 ms 4940 KB Output is correct
85 Correct 86 ms 4900 KB Output is correct
86 Correct 81 ms 5012 KB Output is correct
87 Correct 87 ms 5052 KB Output is correct
88 Correct 90 ms 4948 KB Output is correct
89 Correct 88 ms 4940 KB Output is correct
90 Correct 90 ms 4940 KB Output is correct
91 Correct 92 ms 4948 KB Output is correct
92 Correct 118 ms 4816 KB Output is correct