oj.uz

Submission #442321

# Submission time Handle Problem Language Result Execution time Memory
442321 2021-07-07T12:45:56 Z Haidara Mecho (IOI09_mecho) C++17
4 / 100
 408 ms 7240 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';
}
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(valid(x,y))
            {
                if(dist[f.ff][f.ss]+jump<dist[x][y])
                    dist[x][y]=dist[f.ff][f.ss]+jump,q.push({x,y});
            }
        }
    }
}
bool check(int st)
{
    queue<p(pii,int)>qq;
    qq.push({M,st*jump});
    bool vis[maxn][maxn];
    FOR(i,maxn)
    FOR(j,maxn)
    vis[i][j]=0;
    bool ret=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)
            ret=1;
        FOR(i,4)
        {
            int x=f.ff+dx[i],y=f.ss+dy[i];
            if(valid(x,y)&&a[x][y]!='D')
            {
                if(dist[x][y]>curr+1&&!vis[x][y])
                    qq.push({{x,y},curr+1}),vis[x][y]=1;
            }
        }
    }
    return ret;
}
signed main()
{
    SIO("");
    cin>>n>>jump;
    FOR(i,n)
    FOR(j,n)
    {
        dist[i][j]=inf;
        cin>>a[i][j];
        if(a[i][j]=='M')
            M= {i,j};
        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=0,r=inf,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 '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
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 844 KB Output isn't correct
2 Incorrect 2 ms 844 KB Output isn't correct
3 Incorrect 2 ms 960 KB Output isn't correct
4 Incorrect 2 ms 844 KB Output isn't correct
5 Incorrect 2 ms 972 KB Output isn't correct
6 Incorrect 2 ms 972 KB Output isn't correct
7 Incorrect 211 ms 6840 KB Output isn't correct
8 Correct 2 ms 972 KB Output is correct
9 Incorrect 2 ms 972 KB Output isn't correct
10 Incorrect 2 ms 972 KB Output isn't correct
11 Incorrect 2 ms 972 KB Output isn't correct
12 Incorrect 3 ms 1228 KB Output isn't correct
13 Incorrect 3 ms 1100 KB Output isn't correct
14 Correct 3 ms 1228 KB Output is correct
15 Incorrect 2 ms 972 KB Output isn't correct
16 Incorrect 2 ms 972 KB Output isn't correct
17 Incorrect 2 ms 972 KB Output isn't correct
18 Incorrect 2 ms 972 KB Output isn't correct
19 Incorrect 3 ms 972 KB Output isn't correct
20 Incorrect 3 ms 972 KB Output isn't correct
21 Incorrect 3 ms 1100 KB Output isn't correct
22 Incorrect 3 ms 1100 KB Output isn't correct
23 Incorrect 3 ms 1100 KB Output isn't correct
24 Incorrect 3 ms 1100 KB Output isn't correct
25 Incorrect 3 ms 1228 KB Output isn't correct
26 Incorrect 4 ms 1228 KB Output isn't correct
27 Incorrect 3 ms 1228 KB Output isn't correct
28 Incorrect 4 ms 1228 KB Output isn't correct
29 Incorrect 3 ms 1228 KB Output isn't correct
30 Incorrect 4 ms 1228 KB Output isn't correct
31 Incorrect 3 ms 1228 KB Output isn't correct
32 Incorrect 4 ms 1228 KB Output isn't correct
33 Incorrect 26 ms 3424 KB Output isn't correct
34 Incorrect 43 ms 3404 KB Output isn't correct
35 Incorrect 53 ms 3424 KB Output isn't correct
36 Incorrect 33 ms 3660 KB Output isn't correct
37 Incorrect 53 ms 3704 KB Output isn't correct
38 Incorrect 63 ms 3788 KB Output isn't correct
39 Incorrect 40 ms 4036 KB Output isn't correct
40 Incorrect 70 ms 4112 KB Output isn't correct
41 Incorrect 76 ms 4128 KB Output isn't correct
42 Incorrect 51 ms 4388 KB Output isn't correct
43 Incorrect 91 ms 4480 KB Output isn't correct
44 Incorrect 118 ms 4500 KB Output isn't correct
45 Incorrect 61 ms 4812 KB Output isn't correct
46 Incorrect 106 ms 4848 KB Output isn't correct
47 Incorrect 118 ms 4824 KB Output isn't correct
48 Incorrect 70 ms 5188 KB Output isn't correct
49 Incorrect 124 ms 5184 KB Output isn't correct
50 Incorrect 150 ms 5120 KB Output isn't correct
51 Incorrect 84 ms 5572 KB Output isn't correct
52 Incorrect 141 ms 5524 KB Output isn't correct
53 Incorrect 167 ms 5660 KB Output isn't correct
54 Incorrect 96 ms 5840 KB Output isn't correct
55 Incorrect 185 ms 5892 KB Output isn't correct
56 Incorrect 260 ms 6012 KB Output isn't correct
57 Incorrect 113 ms 6340 KB Output isn't correct
58 Incorrect 209 ms 6152 KB Output isn't correct
59 Incorrect 291 ms 6264 KB Output isn't correct
60 Incorrect 130 ms 6560 KB Output isn't correct
61 Incorrect 220 ms 6608 KB Output isn't correct
62 Incorrect 321 ms 6520 KB Output isn't correct
63 Incorrect 161 ms 6720 KB Output isn't correct
64 Incorrect 408 ms 6612 KB Output isn't correct
65 Incorrect 286 ms 6596 KB Output isn't correct
66 Incorrect 213 ms 6612 KB Output isn't correct
67 Correct 174 ms 6524 KB Output is correct
68 Incorrect 134 ms 6640 KB Output isn't correct
69 Incorrect 122 ms 6664 KB Output isn't correct
70 Incorrect 105 ms 6596 KB Output isn't correct
71 Incorrect 124 ms 6552 KB Output isn't correct
72 Incorrect 132 ms 6596 KB Output isn't correct
73 Incorrect 106 ms 7160 KB Output isn't correct
74 Incorrect 308 ms 7132 KB Output isn't correct
75 Incorrect 156 ms 7108 KB Output isn't correct
76 Incorrect 146 ms 7240 KB Output isn't correct
77 Incorrect 193 ms 7072 KB Output isn't correct
78 Correct 193 ms 7108 KB Output is correct
79 Incorrect 237 ms 7096 KB Output isn't correct
80 Incorrect 190 ms 7112 KB Output isn't correct
81 Incorrect 159 ms 7104 KB Output isn't correct
82 Incorrect 188 ms 6980 KB Output isn't correct
83 Incorrect 203 ms 7108 KB Output isn't correct
84 Incorrect 308 ms 7108 KB Output isn't correct
85 Incorrect 181 ms 6904 KB Output isn't correct
86 Incorrect 169 ms 7036 KB Output isn't correct
87 Incorrect 233 ms 7096 KB Output isn't correct
88 Incorrect 184 ms 6892 KB Output isn't correct
89 Incorrect 288 ms 6904 KB Output isn't correct
90 Incorrect 228 ms 6952 KB Output isn't correct
91 Incorrect 235 ms 6852 KB Output isn't correct
92 Incorrect 241 ms 6940 KB Output isn't correct