oj.uz

Submission #472734

# Submission time Handle Problem Language Result Execution time Memory
472734 2021-09-14T08:55:36 Z hackerbhaiya Mecho (IOI09_mecho) C++14
53 / 100
 448 ms 11312 KB 
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
// ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(i,1,z+1)
    {
        //cout<<"Case #"<<i<<": ";
        ll n,d,sx,sy,fx,fy;
        int dx[]={0,1,0,-1};
        int dy[]={1,0,-1,0};
        cin>>n>>d;
        vector<string> s(n);
        f(i,0,n)
            cin>>s[i];
        ll l=0,r=2*n+5;
        queue<vector<ll> > q;
        vector<vector<ll> > dis(n,vector<ll> (n,inf));
        f(i,0,n)
        {
            f(j,0,n)
            {
                if(s[i][j]=='H')
                    q.push({i,j}),dis[i][j]=0;
                else if(s[i][j]=='M')
                    sx=i,sy=j;
                else if(s[i][j]=='D')
                    fx=i,fy=j;
            }
        }
        while(!q.empty())
        {
            auto temp=q.front();
            q.pop();
            ll x=temp[0],y=temp[1];
            f(i,0,4)
            {
                ll xx=x+dx[i],yy=y+dy[i];
                if(xx>=0 && yy>=0 && xx<n && yy<n && s[xx][yy]!='T' && dis[xx][yy]>d+dis[x][y])
                    dis[xx][yy]=d+dis[x][y],q.push({xx,yy});             
            }
        }
        while(l<=r)
        {
            ll mid=(l+r)/2;
            queue<vector<ll> > q;
            vector<vector<ll> > dis2(n,vector<ll> (n,inf));
            if(dis[sx][sy]>mid*d)
                q.push({sx,sy});
            dis2[sx][sy]=mid*d;
            while(!q.empty())
            {
                auto temp=q.front();
                q.pop();
                ll x=temp[0],y=temp[1];
                if(x==fx && y==fy)
                    break;
                f(i,0,4)
                {
                    ll xx=x+dx[i],yy=y+dy[i];
                    if(xx>=0 && yy>=0 && xx<n && yy<n && s[xx][yy]!='T' && dis2[xx][yy]>1+dis2[x][y])
                    {
                        if((xx==fx && yy==fy) || (1+dis2[x][y]<dis[xx][yy]))
                            dis2[xx][yy]=1+dis2[x][y],q.push({xx,yy});       
                    }
                }
            }
            if(dis2[fx][fy]<inf)
                l=mid+1;
            else
                r=mid-1;
        }
        cout<<r<<"\n";
    }
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:116:27: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |             if(dis2[fx][fy]<inf)
      |                           ^
mecho.cpp:116:23: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |             if(dis2[fx][fy]<inf)
      |                       ^
mecho.cpp:96:26: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |             if(dis[sx][sy]>mid*d)
      |                          ^
mecho.cpp:96:22: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |             if(dis[sx][sy]>mid*d)
      |                      ^

Subtask #1
53.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 316 ms 11156 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Incorrect 1 ms 204 KB Output isn't correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Incorrect 1 ms 204 KB Output isn't correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Incorrect 1 ms 332 KB Output isn't correct
23 Incorrect 1 ms 332 KB Output isn't correct
24 Incorrect 1 ms 344 KB Output isn't correct
25 Incorrect 1 ms 332 KB Output isn't correct
26 Incorrect 1 ms 332 KB Output isn't correct
27 Incorrect 1 ms 332 KB Output isn't correct
28 Incorrect 1 ms 332 KB Output isn't correct
29 Incorrect 1 ms 332 KB Output isn't correct
30 Incorrect 1 ms 332 KB Output isn't correct
31 Incorrect 1 ms 332 KB Output isn't correct
32 Incorrect 1 ms 332 KB Output isn't correct
33 Incorrect 10 ms 2400 KB Output isn't correct
34 Incorrect 11 ms 2396 KB Output isn't correct
35 Correct 69 ms 2400 KB Output is correct
36 Incorrect 13 ms 3020 KB Output isn't correct
37 Incorrect 14 ms 3044 KB Output isn't correct
38 Correct 87 ms 3052 KB Output is correct
39 Incorrect 17 ms 3744 KB Output isn't correct
40 Incorrect 18 ms 3760 KB Output isn't correct
41 Correct 116 ms 3768 KB Output is correct
42 Incorrect 20 ms 4564 KB Output isn't correct
43 Incorrect 22 ms 4676 KB Output isn't correct
44 Correct 146 ms 4560 KB Output is correct
45 Incorrect 25 ms 5436 KB Output isn't correct
46 Incorrect 28 ms 5432 KB Output isn't correct
47 Correct 175 ms 5420 KB Output is correct
48 Incorrect 31 ms 6432 KB Output isn't correct
49 Incorrect 32 ms 6400 KB Output isn't correct
50 Correct 217 ms 6568 KB Output is correct
51 Incorrect 35 ms 7460 KB Output isn't correct
52 Incorrect 38 ms 7468 KB Output isn't correct
53 Correct 264 ms 7380 KB Output is correct
54 Incorrect 40 ms 8612 KB Output isn't correct
55 Incorrect 42 ms 8628 KB Output isn't correct
56 Correct 310 ms 8568 KB Output is correct
57 Incorrect 45 ms 9848 KB Output isn't correct
58 Incorrect 49 ms 9844 KB Output isn't correct
59 Correct 362 ms 9924 KB Output is correct
60 Incorrect 51 ms 11148 KB Output isn't correct
61 Incorrect 54 ms 11156 KB Output isn't correct
62 Correct 448 ms 11124 KB Output is correct
63 Correct 287 ms 11084 KB Output is correct
64 Correct 432 ms 11108 KB Output is correct
65 Correct 407 ms 11104 KB Output is correct
66 Correct 312 ms 11096 KB Output is correct
67 Correct 309 ms 11092 KB Output is correct
68 Correct 135 ms 11136 KB Output is correct
69 Correct 117 ms 11172 KB Output is correct
70 Correct 107 ms 11180 KB Output is correct
71 Correct 102 ms 11156 KB Output is correct
72 Correct 84 ms 11200 KB Output is correct
73 Correct 138 ms 11208 KB Output is correct
74 Correct 199 ms 11152 KB Output is correct
75 Correct 222 ms 11196 KB Output is correct
76 Correct 225 ms 11220 KB Output is correct
77 Correct 225 ms 11144 KB Output is correct
78 Correct 258 ms 11192 KB Output is correct
79 Correct 198 ms 11164 KB Output is correct
80 Correct 205 ms 11136 KB Output is correct
81 Correct 270 ms 11312 KB Output is correct
82 Correct 217 ms 11216 KB Output is correct
83 Correct 283 ms 11148 KB Output is correct
84 Correct 266 ms 11200 KB Output is correct
85 Correct 279 ms 11304 KB Output is correct
86 Correct 278 ms 11224 KB Output is correct
87 Correct 267 ms 11148 KB Output is correct
88 Correct 296 ms 11152 KB Output is correct
89 Correct 303 ms 11236 KB Output is correct
90 Correct 313 ms 11144 KB Output is correct
91 Correct 316 ms 11232 KB Output is correct
92 Correct 268 ms 11140 KB Output is correct