oj.uz

답안 #472731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472731 2021-09-14T08:47:32 Z hackerbhaiya Mecho (IOI09_mecho) C++14
56 / 100
 1000 ms 13872 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=1e6;
        while(l<=r)
        {
            ll mid=(l+r)/2;
            queue<vector<ll> > q;
            vector<vector<ll> > dis(n,vector<ll> (n,inf)),dis2(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(!q.empty())
                q.pop();
            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];
                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:114:27: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |             if(dis2[fx][fy]<inf)
      |                           ^
mecho.cpp:114:23: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |             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
56.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Execution timed out 1093 ms 12448 KB Time limit exceeded
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 4 ms 332 KB Output isn't correct
13 Correct 7 ms 332 KB Output is correct
14 Correct 10 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 3 ms 364 KB Output is correct
25 Correct 6 ms 332 KB Output is correct
26 Correct 4 ms 308 KB Output is correct
27 Correct 4 ms 316 KB Output is correct
28 Correct 5 ms 332 KB Output is correct
29 Correct 5 ms 332 KB Output is correct
30 Correct 7 ms 316 KB Output is correct
31 Correct 6 ms 428 KB Output is correct
32 Correct 7 ms 420 KB Output is correct
33 Correct 122 ms 2528 KB Output is correct
34 Correct 149 ms 2548 KB Output is correct
35 Correct 257 ms 2508 KB Output is correct
36 Correct 177 ms 3272 KB Output is correct
37 Correct 168 ms 3176 KB Output is correct
38 Correct 346 ms 3196 KB Output is correct
39 Correct 215 ms 4040 KB Output is correct
40 Correct 221 ms 4036 KB Output is correct
41 Correct 423 ms 3952 KB Output is correct
42 Correct 250 ms 4780 KB Output is correct
43 Correct 280 ms 4824 KB Output is correct
44 Correct 515 ms 4812 KB Output is correct
45 Correct 308 ms 5852 KB Output is correct
46 Correct 336 ms 5724 KB Output is correct
47 Correct 649 ms 5736 KB Output is correct
48 Correct 359 ms 6844 KB Output is correct
49 Correct 411 ms 6764 KB Output is correct
50 Correct 774 ms 6776 KB Output is correct
51 Correct 425 ms 7904 KB Output is correct
52 Correct 471 ms 7944 KB Output is correct
53 Correct 907 ms 8012 KB Output is correct
54 Correct 526 ms 9064 KB Output is correct
55 Correct 542 ms 9168 KB Output is correct
56 Execution timed out 1037 ms 9088 KB Time limit exceeded
57 Correct 567 ms 10580 KB Output is correct
58 Correct 616 ms 10592 KB Output is correct
59 Execution timed out 1090 ms 10316 KB Time limit exceeded
60 Correct 599 ms 11724 KB Output is correct
61 Correct 713 ms 11840 KB Output is correct
62 Execution timed out 1094 ms 11752 KB Time limit exceeded
63 Execution timed out 1083 ms 11724 KB Time limit exceeded
64 Execution timed out 1092 ms 11668 KB Time limit exceeded
65 Execution timed out 1091 ms 11852 KB Time limit exceeded
66 Execution timed out 1087 ms 11724 KB Time limit exceeded
67 Execution timed out 1085 ms 11724 KB Time limit exceeded
68 Execution timed out 1077 ms 11840 KB Time limit exceeded
69 Execution timed out 1091 ms 11852 KB Time limit exceeded
70 Execution timed out 1089 ms 11852 KB Time limit exceeded
71 Execution timed out 1084 ms 11852 KB Time limit exceeded
72 Execution timed out 1083 ms 11972 KB Time limit exceeded
73 Execution timed out 1083 ms 13748 KB Time limit exceeded
74 Execution timed out 1090 ms 13580 KB Time limit exceeded
75 Execution timed out 1077 ms 13788 KB Time limit exceeded
76 Execution timed out 1087 ms 13620 KB Time limit exceeded
77 Execution timed out 1088 ms 13872 KB Time limit exceeded
78 Execution timed out 1079 ms 13492 KB Time limit exceeded
79 Execution timed out 1059 ms 13520 KB Time limit exceeded
80 Execution timed out 1082 ms 13516 KB Time limit exceeded
81 Execution timed out 1061 ms 13688 KB Time limit exceeded
82 Execution timed out 1088 ms 13556 KB Time limit exceeded
83 Execution timed out 1089 ms 13196 KB Time limit exceeded
84 Execution timed out 1091 ms 13124 KB Time limit exceeded
85 Execution timed out 1089 ms 13180 KB Time limit exceeded
86 Execution timed out 1090 ms 12980 KB Time limit exceeded
87 Execution timed out 1072 ms 13132 KB Time limit exceeded
88 Execution timed out 1088 ms 12712 KB Time limit exceeded
89 Execution timed out 1091 ms 13028 KB Time limit exceeded
90 Execution timed out 1090 ms 12800 KB Time limit exceeded
91 Execution timed out 1079 ms 12744 KB Time limit exceeded
92 Execution timed out 1094 ms 12868 KB Time limit exceeded