Submission #442182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442182	2021-07-07T09:07:54 Z	Haidara	Mecho (IOI09_mecho)	C++17	9 / 100	426 ms	12108 KB

mecho

/* * * * * * * * * *\
 * 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;
    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]+1;
                            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

9.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	38 ms	11212 KB	Output isn't correct
2	Incorrect	45 ms	11212 KB	Output isn't correct
3	Incorrect	41 ms	11136 KB	Output isn't correct
4	Incorrect	39 ms	11200 KB	Output isn't correct
5	Incorrect	38 ms	11212 KB	Output isn't correct
6	Incorrect	41 ms	11212 KB	Output isn't correct
7	Incorrect	233 ms	11900 KB	Output isn't correct
8	Incorrect	38 ms	11212 KB	Output isn't correct
9	Correct	43 ms	11212 KB	Output is correct
10	Incorrect	38 ms	11228 KB	Output isn't correct
11	Incorrect	41 ms	11212 KB	Output isn't correct
12	Incorrect	46 ms	11212 KB	Output isn't correct
13	Incorrect	70 ms	11384 KB	Output isn't correct
14	Incorrect	71 ms	11500 KB	Output isn't correct
15	Incorrect	39 ms	11212 KB	Output isn't correct
16	Correct	42 ms	11212 KB	Output is correct
17	Incorrect	38 ms	11212 KB	Output isn't correct
18	Correct	37 ms	11212 KB	Output is correct
19	Incorrect	39 ms	11240 KB	Output isn't correct
20	Correct	39 ms	11212 KB	Output is correct
21	Incorrect	40 ms	11248 KB	Output isn't correct
22	Correct	39 ms	11232 KB	Output is correct
23	Incorrect	38 ms	11252 KB	Output isn't correct
24	Correct	40 ms	11232 KB	Output is correct
25	Incorrect	42 ms	11264 KB	Output isn't correct
26	Correct	43 ms	11232 KB	Output is correct
27	Incorrect	45 ms	11268 KB	Output isn't correct
28	Correct	42 ms	11212 KB	Output is correct
29	Incorrect	40 ms	11268 KB	Output isn't correct
30	Correct	41 ms	11272 KB	Output is correct
31	Incorrect	44 ms	11220 KB	Output isn't correct
32	Correct	41 ms	11212 KB	Output is correct
33	Incorrect	56 ms	11488 KB	Output isn't correct
34	Correct	55 ms	11364 KB	Output is correct
35	Correct	106 ms	11520 KB	Output is correct
36	Incorrect	56 ms	11468 KB	Output isn't correct
37	Correct	60 ms	11468 KB	Output is correct
38	Correct	107 ms	11636 KB	Output is correct
39	Incorrect	55 ms	11552 KB	Output isn't correct
40	Correct	55 ms	11520 KB	Output is correct
41	Correct	118 ms	11656 KB	Output is correct
42	Incorrect	65 ms	11664 KB	Output isn't correct
43	Correct	61 ms	11596 KB	Output is correct
44	Correct	133 ms	11648 KB	Output is correct
45	Incorrect	65 ms	11588 KB	Output isn't correct
46	Correct	66 ms	11596 KB	Output is correct
47	Correct	153 ms	11744 KB	Output is correct
48	Incorrect	72 ms	11760 KB	Output isn't correct
49	Correct	71 ms	11588 KB	Output is correct
50	Correct	167 ms	11736 KB	Output is correct
51	Incorrect	72 ms	11712 KB	Output isn't correct
52	Correct	73 ms	11708 KB	Output is correct
53	Correct	212 ms	11768 KB	Output is correct
54	Incorrect	83 ms	11716 KB	Output isn't correct
55	Correct	79 ms	11756 KB	Output is correct
56	Correct	238 ms	11852 KB	Output is correct
57	Incorrect	86 ms	11724 KB	Output isn't correct
58	Correct	93 ms	11792 KB	Output is correct
59	Correct	280 ms	11836 KB	Output is correct
60	Incorrect	101 ms	11728 KB	Output isn't correct
61	Correct	109 ms	11936 KB	Output is correct
62	Correct	316 ms	11880 KB	Output is correct
63	Incorrect	401 ms	11880 KB	Output isn't correct
64	Correct	426 ms	11856 KB	Output is correct
65	Incorrect	381 ms	11868 KB	Output isn't correct
66	Incorrect	314 ms	11844 KB	Output isn't correct
67	Incorrect	365 ms	11872 KB	Output isn't correct
68	Incorrect	265 ms	11892 KB	Output isn't correct
69	Correct	218 ms	11868 KB	Output is correct
70	Incorrect	200 ms	11900 KB	Output isn't correct
71	Incorrect	212 ms	11940 KB	Output isn't correct
72	Incorrect	196 ms	11824 KB	Output isn't correct
73	Incorrect	196 ms	11936 KB	Output isn't correct
74	Correct	182 ms	11956 KB	Output is correct
75	Incorrect	192 ms	11960 KB	Output isn't correct
76	Incorrect	181 ms	11908 KB	Output isn't correct
77	Incorrect	183 ms	11948 KB	Output isn't correct
78	Incorrect	205 ms	11952 KB	Output isn't correct
79	Correct	164 ms	12060 KB	Output is correct
80	Incorrect	187 ms	11936 KB	Output isn't correct
81	Incorrect	194 ms	11956 KB	Output isn't correct
82	Incorrect	178 ms	12020 KB	Output isn't correct
83	Incorrect	231 ms	11948 KB	Output isn't correct
84	Correct	221 ms	11928 KB	Output is correct
85	Incorrect	210 ms	11944 KB	Output isn't correct
86	Incorrect	226 ms	11960 KB	Output isn't correct
87	Correct	212 ms	11960 KB	Output is correct
88	Incorrect	231 ms	11972 KB	Output isn't correct
89	Correct	242 ms	11968 KB	Output is correct
90	Correct	251 ms	12020 KB	Output is correct
91	Correct	233 ms	12108 KB	Output is correct
92	Incorrect	242 ms	11928 KB	Output isn't correct