oj.uz

Submission #263484

# Submission time Handle Problem Language Result Execution time Memory
263484 2020-08-13T17:43:50 Z uacoder123 Mecho (IOI09_mecho) C++14
0 / 100
 18 ms 10624 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)

typedef long long int lli;
typedef pair <int, int> df;
typedef vector <int> vi;

int te,n,s;pair<int,int> pob,poh;
char grid[800][800];
int tobc[800][800];
int visited[800][800];
pair<int,int> movearr[] = {{0,-1},{1,0},{0,1},{-1,0}};

int canmove(const pair<int,int>& pos, const pair<int,int>& ptom, const int& bearob)
{
    if(ptom.S>=n||ptom.S<0||ptom.F>=n||ptom.F<0||grid[ptom.F][ptom.S]=='T')
        return(0);
    if(bearob==0&&grid[ptom.F][ptom.S]=='D')
        return(0);
  
    return(1);
}

int check(int t,int r)
{
    if(tobc[pob.F][pob.S] <= t) return 0;
    memset(visited, 0, sizeof(visited));
    int maccom=0,step=0;
    queue<pair<int,int>> sp1,sp2;
    sp1.push(pob);
    visited[pob.F][pob.S]=1;
    while(sp1.size()!=0)
    {
        pair<int,int> pos=sp1.front();
        for(int i=0;i<4;++i)
        {
            int x=pos.F+movearr[i].F,y=pos.S+movearr[i].S;
            if(canmove(pos,{x, y},1) && !visited[x][y] )
            {
                if(tobc[x][y]>t&&(step!=s-1||tobc[x][y]!=t+1))
                {
                    sp2.push({x,y});
                    visited[x][y]=1;
                    if(mp(x,y)==poh)
                    {
                        maccom++;
                    }
                }
            }
        }
        sp1.pop();
        if(sp1.size()==0)
        {
            step = (1 + step)%s;
            if(!step) ++t;
            swap(sp1,sp2);
        }
    }
    return(maccom);
}

void bfs1(vector<pair<int,int>> pos_vec)
{
    memset(visited, 0, sizeof(visited));
    queue<pair<int,int>> q;
    for(uint i=0;i<pos_vec.size();++i) 
    {
        q.push(pos_vec[i]);
        visited[pos_vec[i].F][pos_vec[i].S]=1;
    }
        
    while(q.size())
    {
        pair<int,int> pos=q.front();
        for(int i=0;i<4;++i)
        {
            int x=pos.F+movearr[i].F,y=pos.S+movearr[i].S;
            if(canmove(pos,{x,y},0) && !visited[x][y])
            {
                q.push({x,y});
                visited[x][y]=1;
                tobc[x][y]=min(tobc[x][y],tobc[pos.F][pos.S]+1);
            }
        }
        q.pop();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    te=1;
    cin>>te;
    for(;te>0;--te)
    {
     cin>>n>>s;   
     vector<pair<int,int>> pobees; 
     for(int i=0;i<n;++i)
     {
        for(int i1=0;i1<n;++i1)
            {
                tobc[i][i1]=650000;
                cin>>grid[i][i1];
                if(grid[i][i1]=='M')
                    pob={i,i1};
                else if(grid[i][i1]=='D')
                    poh={i,i1};
                else if(grid[i][i1]=='H')
                   {
                    pobees.pb(mp(i,i1));
                    tobc[i][i1]=0;
                   }
            }
     }   

     bfs1(pobees);
     int r=n*n,l=0,ans=-1;
     while(l<=r)
     {
        int mid=(l+r+1)/2;
        if(check(mid,r))
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
     }
     cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
3 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Runtime error 6 ms 5492 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
6 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
7 Runtime error 6 ms 5888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
8 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
9 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
10 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
11 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
12 Runtime error 7 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
13 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
15 Runtime error 7 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
16 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
17 Runtime error 7 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
18 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
19 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
20 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
21 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
22 Runtime error 7 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
23 Runtime error 8 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
24 Runtime error 8 ms 5736 KB Execution killed with signal 8 (could be triggered by violating memory limits)
25 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
26 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
27 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
28 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
29 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
30 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
31 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
32 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
33 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
34 Runtime error 7 ms 6656 KB Execution killed with signal 8 (could be triggered by violating memory limits)
35 Runtime error 9 ms 7808 KB Execution killed with signal 8 (could be triggered by violating memory limits)
36 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
37 Runtime error 7 ms 6784 KB Execution killed with signal 8 (could be triggered by violating memory limits)
38 Runtime error 10 ms 8064 KB Execution killed with signal 8 (could be triggered by violating memory limits)
39 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
40 Runtime error 8 ms 7040 KB Execution killed with signal 8 (could be triggered by violating memory limits)
41 Runtime error 13 ms 8448 KB Execution killed with signal 8 (could be triggered by violating memory limits)
42 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
43 Runtime error 8 ms 7168 KB Execution killed with signal 8 (could be triggered by violating memory limits)
44 Runtime error 12 ms 8704 KB Execution killed with signal 8 (could be triggered by violating memory limits)
45 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
46 Runtime error 8 ms 7296 KB Execution killed with signal 8 (could be triggered by violating memory limits)
47 Runtime error 13 ms 9052 KB Execution killed with signal 8 (could be triggered by violating memory limits)
48 Runtime error 7 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
49 Runtime error 9 ms 7552 KB Execution killed with signal 8 (could be triggered by violating memory limits)
50 Runtime error 16 ms 9344 KB Execution killed with signal 8 (could be triggered by violating memory limits)
51 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
52 Runtime error 9 ms 7680 KB Execution killed with signal 8 (could be triggered by violating memory limits)
53 Runtime error 15 ms 9728 KB Execution killed with signal 8 (could be triggered by violating memory limits)
54 Runtime error 7 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
55 Runtime error 12 ms 7808 KB Execution killed with signal 8 (could be triggered by violating memory limits)
56 Runtime error 14 ms 9984 KB Execution killed with signal 8 (could be triggered by violating memory limits)
57 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
58 Runtime error 12 ms 7936 KB Execution killed with signal 8 (could be triggered by violating memory limits)
59 Runtime error 18 ms 10496 KB Execution killed with signal 8 (could be triggered by violating memory limits)
60 Runtime error 6 ms 5504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
61 Runtime error 9 ms 8064 KB Execution killed with signal 8 (could be triggered by violating memory limits)
62 Runtime error 17 ms 10624 KB Execution killed with signal 8 (could be triggered by violating memory limits)
63 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
64 Runtime error 13 ms 5736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
66 Runtime error 7 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
67 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
68 Runtime error 7 ms 5888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
69 Runtime error 8 ms 7168 KB Execution killed with signal 8 (could be triggered by violating memory limits)
70 Runtime error 7 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
71 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
72 Runtime error 9 ms 7168 KB Execution killed with signal 8 (could be triggered by violating memory limits)
73 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
74 Runtime error 12 ms 8704 KB Execution killed with signal 8 (could be triggered by violating memory limits)
75 Runtime error 8 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
76 Runtime error 7 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
77 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
78 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
79 Runtime error 13 ms 8960 KB Execution killed with signal 8 (could be triggered by violating memory limits)
80 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
81 Runtime error 7 ms 5656 KB Execution killed with signal 8 (could be triggered by violating memory limits)
82 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
83 Runtime error 8 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
84 Runtime error 12 ms 9088 KB Execution killed with signal 8 (could be triggered by violating memory limits)
85 Runtime error 7 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
86 Runtime error 6 ms 5632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
87 Runtime error 6 ms 5888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
88 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)
89 Runtime error 12 ms 9216 KB Execution killed with signal 8 (could be triggered by violating memory limits)
90 Runtime error 6 ms 5888 KB Execution killed with signal 8 (could be triggered by violating memory limits)
91 Runtime error 6 ms 6144 KB Execution killed with signal 8 (could be triggered by violating memory limits)
92 Runtime error 6 ms 5760 KB Execution killed with signal 8 (could be triggered by violating memory limits)