oj.uz

Submission #442180

# Submission time Handle Problem Language Result Execution time Memory
442180 2021-07-07T09:05:48 Z Haidara Mecho (IOI09_mecho) C++17
6 / 100
 399 ms 12076 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]=0;
    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]+Time)
                        {
                            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+Time)
                        {
                            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
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 11212 KB Output isn't correct
2 Incorrect 40 ms 11212 KB Output isn't correct
3 Incorrect 41 ms 11212 KB Output isn't correct
4 Incorrect 46 ms 11212 KB Output isn't correct
5 Incorrect 39 ms 11204 KB Output isn't correct
6 Incorrect 42 ms 11212 KB Output isn't correct
7 Incorrect 261 ms 11924 KB Output isn't correct
8 Incorrect 40 ms 11212 KB Output isn't correct
9 Correct 59 ms 11212 KB Output is correct
10 Incorrect 59 ms 11212 KB Output isn't correct
11 Incorrect 44 ms 11212 KB Output isn't correct
12 Incorrect 41 ms 11212 KB Output isn't correct
13 Incorrect 88 ms 11284 KB Output isn't correct
14 Incorrect 73 ms 11296 KB Output isn't correct
15 Incorrect 48 ms 11212 KB Output isn't correct
16 Correct 49 ms 11212 KB Output is correct
17 Incorrect 40 ms 11212 KB Output isn't correct
18 Incorrect 42 ms 11212 KB Output isn't correct
19 Incorrect 40 ms 11232 KB Output isn't correct
20 Correct 45 ms 11212 KB Output is correct
21 Incorrect 43 ms 11236 KB Output isn't correct
22 Correct 41 ms 11212 KB Output is correct
23 Incorrect 39 ms 11252 KB Output isn't correct
24 Correct 40 ms 11260 KB Output is correct
25 Incorrect 41 ms 11252 KB Output isn't correct
26 Correct 40 ms 11212 KB Output is correct
27 Incorrect 40 ms 11248 KB Output isn't correct
28 Incorrect 44 ms 11268 KB Output isn't correct
29 Incorrect 40 ms 11264 KB Output isn't correct
30 Correct 44 ms 11272 KB Output is correct
31 Incorrect 50 ms 11280 KB Output isn't correct
32 Incorrect 38 ms 11268 KB Output isn't correct
33 Incorrect 51 ms 11492 KB Output isn't correct
34 Correct 51 ms 11468 KB Output is correct
35 Incorrect 100 ms 11524 KB Output isn't correct
36 Incorrect 54 ms 11468 KB Output isn't correct
37 Correct 57 ms 11468 KB Output is correct
38 Incorrect 109 ms 11564 KB Output isn't correct
39 Incorrect 55 ms 11484 KB Output isn't correct
40 Correct 57 ms 11468 KB Output is correct
41 Incorrect 124 ms 11648 KB Output isn't correct
42 Incorrect 62 ms 11596 KB Output isn't correct
43 Correct 61 ms 11588 KB Output is correct
44 Incorrect 150 ms 11644 KB Output isn't correct
45 Incorrect 68 ms 11596 KB Output isn't correct
46 Correct 66 ms 11596 KB Output is correct
47 Incorrect 157 ms 11784 KB Output isn't correct
48 Incorrect 68 ms 11600 KB Output isn't correct
49 Correct 74 ms 11648 KB Output is correct
50 Incorrect 166 ms 11736 KB Output isn't correct
51 Incorrect 73 ms 11624 KB Output isn't correct
52 Correct 79 ms 11712 KB Output is correct
53 Incorrect 199 ms 11792 KB Output isn't correct
54 Incorrect 85 ms 11648 KB Output isn't correct
55 Correct 92 ms 11700 KB Output is correct
56 Incorrect 223 ms 11820 KB Output isn't correct
57 Incorrect 92 ms 11788 KB Output isn't correct
58 Correct 90 ms 11788 KB Output is correct
59 Incorrect 294 ms 11840 KB Output isn't correct
60 Incorrect 99 ms 11764 KB Output isn't correct
61 Correct 101 ms 11756 KB Output is correct
62 Incorrect 355 ms 11948 KB Output isn't correct
63 Incorrect 353 ms 11892 KB Output isn't correct
64 Incorrect 399 ms 11864 KB Output isn't correct
65 Incorrect 395 ms 11864 KB Output isn't correct
66 Incorrect 346 ms 12028 KB Output isn't correct
67 Incorrect 368 ms 11880 KB Output isn't correct
68 Incorrect 225 ms 12076 KB Output isn't correct
69 Correct 213 ms 11904 KB Output is correct
70 Incorrect 209 ms 11892 KB Output isn't correct
71 Incorrect 216 ms 11912 KB Output isn't correct
72 Incorrect 203 ms 12020 KB Output isn't correct
73 Incorrect 188 ms 11916 KB Output isn't correct
74 Incorrect 188 ms 12032 KB Output isn't correct
75 Incorrect 217 ms 11972 KB Output isn't correct
76 Incorrect 176 ms 11888 KB Output isn't correct
77 Incorrect 191 ms 11996 KB Output isn't correct
78 Incorrect 237 ms 11932 KB Output isn't correct
79 Incorrect 170 ms 11952 KB Output isn't correct
80 Incorrect 168 ms 11964 KB Output isn't correct
81 Incorrect 182 ms 11952 KB Output isn't correct
82 Incorrect 179 ms 11996 KB Output isn't correct
83 Incorrect 267 ms 11916 KB Output isn't correct
84 Incorrect 207 ms 11952 KB Output isn't correct
85 Incorrect 198 ms 11936 KB Output isn't correct
86 Incorrect 219 ms 11932 KB Output isn't correct
87 Incorrect 215 ms 11924 KB Output isn't correct
88 Incorrect 268 ms 12068 KB Output isn't correct
89 Incorrect 268 ms 11900 KB Output isn't correct
90 Incorrect 228 ms 11888 KB Output isn't correct
91 Incorrect 236 ms 11908 KB Output isn't correct
92 Incorrect 240 ms 11936 KB Output isn't correct