oj.uz

Submission #442335

# Submission time Handle Problem Language Result Execution time Memory
442335 2021-07-07T13:15:41 Z Haidara Mecho (IOI09_mecho) C++17
0 / 100
 209 ms 65540 KB 
/* * * * * * * * * *\
 * Author: Haidara *
 * LANG: C++17     *
 * PROB:           *
\* * * * * * * * * */
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define rep(i,x,n) for(int i=x;i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=x;i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define pq(i) priority_queue< i >
#define ff first
#define all(x) x.begin(),x.end()
#define ss second
#define pp push_back
using namespace std;
void SIO(string name="")
{
    if(name!="")
    {
        freopen((name+".in").c_str(),"r",stdin);
        freopen((name+".out").c_str(),"w",stdout);
    }
}
const int inf=1LL<<62LL;
const int mod=1e9+7;
const int maxn=808;
char a[maxn][maxn];
int n,jump;
pii M,D;
queue<pii>q;
int dist[maxn][maxn],dx[] {-1,1,0,0},dy[] {0,0,1,-1};
bool valid(int x,int y)
{
    return x>=0&&y>=0&&x<n&&y<n&&a[x][y]!='T'&&a[x][y]!='H';
}
void solve()
{
    while(q.size())
    {
        pii f=q.front();
        q.pop();
        FOR(i,4)
        {
            int x=f.ff+dx[i],y=f.ss+dy[i];
            if(x>=0&&y>=0&&x<n&&y<n&&a[x][y]=='G'&&dist[x][y]==inf)
                dist[x][y]=dist[f.ff][f.ss]+jump,q.push({x,y});
        }
    }
}
bool check(int st)
{
    queue<p(pii,int)>qq;
    if(st*jump>=dist[M.ff][M.ss])
        return 0;
    qq.push({M,st*jump});
    bool vis[maxn][maxn];
    FOR(i,maxn)
    FOR(j,maxn)
    vis[i][j]=0;
    vis[M.ff][M.ss]=1;
    while(qq.size())
    {
        pii f=qq.front().ff;
        int curr=qq.front().ss;
        qq.pop();
        if(f==D)
            return 1;
        FOR(i,4)
        {
            int x=f.ff+dx[i],y=f.ss+dy[i];
            if(valid(x,y)||dist[x][y]<=curr+1&&vis[x][y])
                continue;
            qq.push({{x,y},curr+1}),vis[x][y]=1;
        }
    }
    return 0;
}
signed main()
{
    SIO("");
    cin>>n>>jump;
    FOR(i,n)
    {
        cin>>ws;
        FOR(j,n)
        {
            dist[i][j]=inf;
            cin>>a[i][j];
            if(a[i][j]=='M')
                M= {i,j},a[i][j]='G';
            else if(a[i][j]=='D')
                D= {i,j};
            else if(a[i][j]=='H')
                q.push({i,j}),dist[i][j]=0;
        }
    }
    solve();
    int l=1,r=maxn*maxn*2,ans=-1;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        if(check(mid))
            ans=max(ans,mid),l=mid+1;
        else
            r=mid-1;
    }
    cout<<ans;
}

Compilation message

mecho.cpp: In function 'bool check(long long int)':
mecho.cpp:79:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |             if(valid(x,y)||dist[x][y]<=curr+1&&vis[x][y])
      |                            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
mecho.cpp: In function 'void SIO(std::string)':
mecho.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1680 KB Execution killed with signal 11
2 Runtime error 2 ms 1740 KB Execution killed with signal 11
3 Runtime error 2 ms 1740 KB Execution killed with signal 11
4 Runtime error 2 ms 1740 KB Execution killed with signal 11
5 Runtime error 2 ms 1740 KB Execution killed with signal 11
6 Runtime error 2 ms 1740 KB Execution killed with signal 11
7 Runtime error 70 ms 13672 KB Execution killed with signal 6
8 Runtime error 2 ms 1740 KB Execution killed with signal 11
9 Runtime error 2 ms 1740 KB Execution killed with signal 11
10 Runtime error 2 ms 1740 KB Execution killed with signal 11
11 Runtime error 2 ms 1740 KB Execution killed with signal 11
12 Runtime error 3 ms 2380 KB Execution killed with signal 11
13 Incorrect 1 ms 1100 KB Output isn't correct
14 Runtime error 126 ms 65540 KB Execution killed with signal 9
15 Runtime error 2 ms 1868 KB Execution killed with signal 11
16 Runtime error 2 ms 1832 KB Execution killed with signal 11
17 Runtime error 2 ms 1868 KB Execution killed with signal 11
18 Runtime error 3 ms 2252 KB Execution killed with signal 11
19 Runtime error 2 ms 1996 KB Execution killed with signal 11
20 Runtime error 9 ms 6860 KB Execution killed with signal 11
21 Runtime error 2 ms 2124 KB Execution killed with signal 11
22 Runtime error 131 ms 65540 KB Execution killed with signal 9
23 Runtime error 3 ms 2124 KB Execution killed with signal 11
24 Runtime error 134 ms 65540 KB Execution killed with signal 9
25 Runtime error 3 ms 2252 KB Execution killed with signal 11
26 Runtime error 137 ms 65540 KB Execution killed with signal 9
27 Runtime error 3 ms 2360 KB Execution killed with signal 11
28 Runtime error 132 ms 65540 KB Execution killed with signal 9
29 Runtime error 3 ms 2380 KB Execution killed with signal 11
30 Runtime error 132 ms 65540 KB Execution killed with signal 9
31 Runtime error 3 ms 2508 KB Execution killed with signal 11
32 Runtime error 137 ms 65540 KB Execution killed with signal 9
33 Runtime error 14 ms 6732 KB Execution killed with signal 11
34 Runtime error 136 ms 65540 KB Execution killed with signal 9
35 Runtime error 18 ms 6732 KB Execution killed with signal 11
36 Runtime error 17 ms 7428 KB Execution killed with signal 11
37 Runtime error 141 ms 65540 KB Execution killed with signal 9
38 Runtime error 19 ms 7448 KB Execution killed with signal 11
39 Runtime error 21 ms 8100 KB Execution killed with signal 11
40 Runtime error 149 ms 65540 KB Execution killed with signal 9
41 Runtime error 24 ms 8104 KB Execution killed with signal 11
42 Runtime error 26 ms 8852 KB Execution killed with signal 11
43 Runtime error 150 ms 65540 KB Execution killed with signal 9
44 Runtime error 27 ms 8876 KB Execution killed with signal 11
45 Runtime error 29 ms 9584 KB Execution killed with signal 11
46 Runtime error 151 ms 65540 KB Execution killed with signal 9
47 Runtime error 32 ms 9512 KB Execution killed with signal 11
48 Runtime error 33 ms 10320 KB Execution killed with signal 11
49 Runtime error 155 ms 65540 KB Execution killed with signal 9
50 Runtime error 38 ms 10264 KB Execution killed with signal 11
51 Runtime error 39 ms 10948 KB Execution killed with signal 11
52 Runtime error 153 ms 65536 KB Execution killed with signal 9
53 Runtime error 43 ms 10992 KB Execution killed with signal 11
54 Runtime error 45 ms 11728 KB Execution killed with signal 11
55 Runtime error 164 ms 65540 KB Execution killed with signal 9
56 Runtime error 52 ms 11696 KB Execution killed with signal 11
57 Runtime error 50 ms 12396 KB Execution killed with signal 11
58 Runtime error 165 ms 65540 KB Execution killed with signal 9
59 Runtime error 58 ms 12512 KB Execution killed with signal 11
60 Runtime error 59 ms 13220 KB Execution killed with signal 11
61 Runtime error 69 ms 25432 KB Execution killed with signal 11
62 Runtime error 64 ms 13156 KB Execution killed with signal 11
63 Runtime error 67 ms 13352 KB Execution killed with signal 11
64 Runtime error 67 ms 13236 KB Execution killed with signal 11
65 Runtime error 69 ms 15684 KB Execution killed with signal 11
66 Runtime error 70 ms 13196 KB Execution killed with signal 11
67 Runtime error 78 ms 22596 KB Execution killed with signal 11
68 Runtime error 204 ms 65540 KB Execution killed with signal 9
69 Runtime error 199 ms 65536 KB Execution killed with signal 9
70 Runtime error 209 ms 65540 KB Execution killed with signal 9
71 Runtime error 199 ms 65540 KB Execution killed with signal 9
72 Runtime error 189 ms 65540 KB Execution killed with signal 9
73 Runtime error 69 ms 14268 KB Execution killed with signal 11
74 Runtime error 71 ms 14276 KB Execution killed with signal 11
75 Runtime error 69 ms 14324 KB Execution killed with signal 11
76 Runtime error 69 ms 14312 KB Execution killed with signal 11
77 Runtime error 69 ms 14344 KB Execution killed with signal 11
78 Runtime error 70 ms 14224 KB Execution killed with signal 11
79 Runtime error 73 ms 16168 KB Execution killed with signal 11
80 Runtime error 153 ms 65536 KB Execution killed with signal 11
81 Runtime error 73 ms 14532 KB Execution killed with signal 11
82 Runtime error 77 ms 17476 KB Execution killed with signal 11
83 Runtime error 73 ms 14020 KB Execution killed with signal 6
84 Runtime error 72 ms 14148 KB Execution killed with signal 11
85 Runtime error 70 ms 14020 KB Execution killed with signal 6
86 Runtime error 69 ms 14060 KB Execution killed with signal 6
87 Runtime error 72 ms 14092 KB Execution killed with signal 11
88 Runtime error 75 ms 13892 KB Execution killed with signal 6
89 Runtime error 68 ms 13892 KB Execution killed with signal 6
90 Runtime error 70 ms 13816 KB Execution killed with signal 6
91 Runtime error 69 ms 13764 KB Execution killed with signal 11
92 Runtime error 68 ms 13896 KB Execution killed with signal 6