oj.uz

Submission #442176

# Submission time Handle Problem Language Result Execution time Memory
442176 2021-07-07T09:03:21 Z Haidara Mecho (IOI09_mecho) C++17
17 / 100
 383 ms 12068 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<<60LL;
const int mod=1e9+7;
const int maxn=808;
int n,foot;
pii Mecho,House;
char a[maxn][maxn];
bool vis[maxn][maxn];
queue<pii>q;
v(v(int)) dist;
int dx[] {-1,1,0,0};
int dy[] {0,0,-1,1};
bool valid(int x,int y)
{
    return x>=0&&y>=0&&x<n&&y<n&&a[x][y]=='G';
}
bool nvalid(int x,int y)
{
    return x>=0&&y>=0&&x<n&&y<n;
}
bool check(int Time)
{
    v(v(int))newdist;
    newdist=dist;
    FOR(i,maxn)
    FOR(j,maxn)
    {
        vis[i][j]=0;
        if(a[i][j]=='T'||a[i][j]=='H'||a[i][j]=='M')
            vis[i][j]=1;
    }
    queue<p(pii,int)>nq;
    nq.push({Mecho,foot});
    newdist[Mecho.ff][Mecho.ss]=Time+1;
    while(nq.size())
    {
        pii f=nq.front().ff;
        int lft=nq.front().ss;
        nq.pop();
        FOR(i,4)
        {
            int x=f.ff+dx[i],y=f.ss+dy[i];
            if(nvalid(x,y)&&(a[x][y]=='G'||a[x][y]=='D'))
            {
                if(!vis[x][y])
                {
                    if(lft)
                    {
                        if(newdist[x][y]>newdist[f.ff][f.ss])
                        {
                            newdist[x][y]=newdist[f.ff][f.ss];
                            nq.push({{x,y},lft-1});
                            vis[x][y]=1;
                        }
                    }
                    else
                    {
                        if(newdist[x][y]>newdist[f.ff][f.ss]+1)
                        {
                            newdist[x][y]=newdist[f.ff][f.ss];
                            nq.push({{x,y},foot});
                            vis[x][y]=1;
                        }
                    }
                }
            }
        }
    }
    return newdist[House.ff][House.ss]!=inf;
}
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(!vis[x][y])
                {
                    vis[x][y]=1;
                    q.push({x,y});
                    dist[x][y]=dist[f.ff][f.ss]+1;
                }
                else if(dist[x][y]>dist[f.ff][f.ss]+1)
                {
                    dist[x][y]=dist[f.ff][f.ss]+1;
                    q.push({x,y});
                }
            }
        }
    }
}
signed main()
{
    SIO("");
    cin>>n>>foot;
    dist.resize(maxn);
    FOR(i,maxn)
    dist[i].resize(maxn);
    FOR(i,n)
    FOR(j,n)
    {
        cin>>a[i][j];
        dist[i][j]=inf;
        if(a[i][j]=='M')
            Mecho= {i,j};
        else if(a[i][j]=='H')
            q.push({i,j}),vis[i][j]=1,dist[i][j]=0;
        else if(a[i][j]=='T')
            vis[i][j]=1;
        else if(a[i][j]=='D')
        House={i,j};
    }
    solve();
    int l=1,r=800*800,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
17.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11212 KB Output is correct
2 Incorrect 39 ms 11212 KB Output isn't correct
3 Correct 40 ms 11204 KB Output is correct
4 Correct 48 ms 11212 KB Output is correct
5 Incorrect 47 ms 11212 KB Output isn't correct
6 Incorrect 48 ms 11160 KB Output isn't correct
7 Incorrect 252 ms 11952 KB Output isn't correct
8 Incorrect 41 ms 11212 KB Output isn't correct
9 Incorrect 42 ms 11184 KB Output isn't correct
10 Incorrect 41 ms 11212 KB Output isn't correct
11 Incorrect 43 ms 11208 KB Output isn't correct
12 Incorrect 57 ms 11212 KB Output isn't correct
13 Incorrect 68 ms 11316 KB Output isn't correct
14 Incorrect 65 ms 11304 KB Output isn't correct
15 Correct 38 ms 11228 KB Output is correct
16 Incorrect 39 ms 11232 KB Output isn't correct
17 Correct 38 ms 11216 KB Output is correct
18 Correct 48 ms 11108 KB Output is correct
19 Correct 38 ms 11236 KB Output is correct
20 Incorrect 46 ms 11212 KB Output isn't correct
21 Correct 46 ms 11228 KB Output is correct
22 Incorrect 44 ms 11340 KB Output isn't correct
23 Correct 40 ms 11252 KB Output is correct
24 Incorrect 39 ms 11252 KB Output isn't correct
25 Correct 38 ms 11260 KB Output is correct
26 Incorrect 38 ms 11212 KB Output isn't correct
27 Correct 38 ms 11240 KB Output is correct
28 Correct 46 ms 11268 KB Output is correct
29 Correct 40 ms 11272 KB Output is correct
30 Incorrect 46 ms 11268 KB Output isn't correct
31 Correct 40 ms 11280 KB Output is correct
32 Correct 46 ms 11256 KB Output is correct
33 Correct 51 ms 11468 KB Output is correct
34 Incorrect 63 ms 11504 KB Output isn't correct
35 Incorrect 92 ms 11516 KB Output isn't correct
36 Correct 53 ms 11520 KB Output is correct
37 Incorrect 58 ms 11592 KB Output isn't correct
38 Incorrect 105 ms 11616 KB Output isn't correct
39 Correct 61 ms 11556 KB Output is correct
40 Incorrect 56 ms 11468 KB Output isn't correct
41 Incorrect 128 ms 11588 KB Output isn't correct
42 Correct 74 ms 11696 KB Output is correct
43 Incorrect 59 ms 11596 KB Output isn't correct
44 Incorrect 129 ms 11688 KB Output isn't correct
45 Correct 81 ms 11548 KB Output is correct
46 Incorrect 65 ms 11596 KB Output isn't correct
47 Incorrect 163 ms 11740 KB Output isn't correct
48 Correct 76 ms 11696 KB Output is correct
49 Incorrect 79 ms 11588 KB Output isn't correct
50 Incorrect 168 ms 11744 KB Output isn't correct
51 Correct 75 ms 11712 KB Output is correct
52 Incorrect 78 ms 11712 KB Output isn't correct
53 Incorrect 227 ms 11776 KB Output isn't correct
54 Correct 79 ms 11648 KB Output is correct
55 Incorrect 90 ms 11680 KB Output isn't correct
56 Incorrect 240 ms 11832 KB Output isn't correct
57 Correct 139 ms 11792 KB Output is correct
58 Incorrect 90 ms 11716 KB Output isn't correct
59 Incorrect 286 ms 11984 KB Output isn't correct
60 Correct 106 ms 11716 KB Output is correct
61 Incorrect 115 ms 11828 KB Output isn't correct
62 Incorrect 320 ms 11896 KB Output isn't correct
63 Incorrect 358 ms 11904 KB Output isn't correct
64 Correct 381 ms 11904 KB Output is correct
65 Incorrect 383 ms 11900 KB Output isn't correct
66 Incorrect 315 ms 11880 KB Output isn't correct
67 Incorrect 367 ms 11868 KB Output isn't correct
68 Incorrect 216 ms 11888 KB Output isn't correct
69 Incorrect 214 ms 11864 KB Output isn't correct
70 Incorrect 217 ms 11892 KB Output isn't correct
71 Incorrect 220 ms 11868 KB Output isn't correct
72 Incorrect 238 ms 11896 KB Output isn't correct
73 Incorrect 199 ms 11928 KB Output isn't correct
74 Correct 220 ms 12068 KB Output is correct
75 Incorrect 226 ms 11960 KB Output isn't correct
76 Incorrect 202 ms 11888 KB Output isn't correct
77 Incorrect 199 ms 12000 KB Output isn't correct
78 Incorrect 202 ms 12036 KB Output isn't correct
79 Correct 163 ms 11924 KB Output is correct
80 Incorrect 200 ms 11932 KB Output isn't correct
81 Incorrect 180 ms 11956 KB Output isn't correct
82 Incorrect 169 ms 11908 KB Output isn't correct
83 Incorrect 254 ms 11944 KB Output isn't correct
84 Correct 236 ms 11996 KB Output is correct
85 Incorrect 235 ms 11976 KB Output isn't correct
86 Incorrect 223 ms 11936 KB Output isn't correct
87 Incorrect 232 ms 11916 KB Output isn't correct
88 Incorrect 235 ms 11932 KB Output isn't correct
89 Correct 280 ms 11896 KB Output is correct
90 Incorrect 258 ms 11932 KB Output isn't correct
91 Incorrect 237 ms 11948 KB Output isn't correct
92 Incorrect 235 ms 11916 KB Output isn't correct