답안 #57575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57575	2018-07-15T09:22:14 Z	Bodo171	Mecho (IOI09_mecho)	C++14	42 / 100	263 ms	40872 KB

mecho

#include <iostream>
#include <fstream>

using namespace std;
const int nmax=805;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
int d[nmax][nmax],a[nmax][nmax];
string s;
pair<int,int> q[nmax*nmax];
int p,u,n,m,i,j,li,ci,lf,cf,l1,l2,c1,c2,S,ans;
bool ok(int X,int Y)
{
    return (X>=1&&Y>=1&&X<=n&&Y<=n);
}
void bfs()
{
    p=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           if(a[i][j]==0)
             q[++u]={i,j};
    for(p=1;p<=u;p++)
    {
        li=q[p].first;ci=q[p].second;
        for(i=0;i<4;i++)
        {
            lf=li+d1[i];cf=ci+d2[i];
            if(ok(lf,cf)&&a[li][ci]+1<a[lf][cf])
            {
                a[lf][cf]=a[li][ci]+1;
                q[++u]={lf,cf};
            }
        }
    }

}
bool check(int val)
{
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           if(d[i][j]!=-1)
              d[i][j]=0;
    d[l1][c1]=1;
    q[p=u=1]={l1,c1};
    for(p=1;p<=u;p++)
    {
        li=q[p].first;ci=q[p].second;
        if((d[li][ci]-1)/S+val>=a[li][ci]) continue;
        if(li==l2&&ci==c2) return 1;
        for(i=0;i<4;i++)
        {
            lf=li+d1[i];cf=ci+d2[i];
            if(ok(lf,cf)&&(!d[lf][cf]))
            {
                d[lf][cf]=d[li][ci]+1;
                q[++u]={lf,cf};
            }
        }
    }
    return 0;
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n>>S;
    for(i=0;i<=n+1;i++)
        for(j=0;j<=n+1;j++)
           a[i][j]=(1<<30);
    for(i=1;i<=n;i++)
    {
        cin>>s;
        for(j=0;j<n;j++)
        {
            if(s[j]=='T') d[i][j+1]=a[i][j+1]=-1;
            if(s[j]=='M') l1=i,c1=j+1;
            if(s[j]=='D') l2=i,c2=j+1;
            if(s[j]=='H') a[i][j+1]=0;
        }
    }
    bfs();
   for(int pu=10;pu>=0;pu--)
        if(check(ans+(1<<pu)))
           ans+=(1<<pu);
    cout<<ans;
    return 0;
}

Subtask #1

42.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Incorrect	2 ms	496 KB	Output isn't correct
3	Correct	2 ms	588 KB	Output is correct
4	Incorrect	3 ms	588 KB	Output isn't correct
5	Correct	2 ms	752 KB	Output is correct
6	Incorrect	3 ms	752 KB	Output isn't correct
7	Incorrect	165 ms	11320 KB	Output isn't correct
8	Incorrect	2 ms	11320 KB	Output isn't correct
9	Correct	2 ms	11320 KB	Output is correct
10	Correct	2 ms	11320 KB	Output is correct
11	Correct	3 ms	11320 KB	Output is correct
12	Incorrect	3 ms	11320 KB	Output isn't correct
13	Correct	3 ms	11320 KB	Output is correct
14	Incorrect	3 ms	11320 KB	Output isn't correct
15	Correct	3 ms	11320 KB	Output is correct
16	Correct	3 ms	11320 KB	Output is correct
17	Correct	2 ms	11320 KB	Output is correct
18	Correct	2 ms	11320 KB	Output is correct
19	Correct	3 ms	11320 KB	Output is correct
20	Correct	3 ms	11320 KB	Output is correct
21	Correct	3 ms	11320 KB	Output is correct
22	Correct	3 ms	11320 KB	Output is correct
23	Correct	4 ms	11320 KB	Output is correct
24	Correct	3 ms	11320 KB	Output is correct
25	Correct	6 ms	11320 KB	Output is correct
26	Correct	4 ms	11320 KB	Output is correct
27	Correct	4 ms	11320 KB	Output is correct
28	Correct	3 ms	11320 KB	Output is correct
29	Incorrect	4 ms	11320 KB	Output isn't correct
30	Correct	3 ms	11320 KB	Output is correct
31	Incorrect	4 ms	11320 KB	Output isn't correct
32	Correct	4 ms	11320 KB	Output is correct
33	Incorrect	15 ms	11320 KB	Output isn't correct
34	Incorrect	13 ms	11320 KB	Output isn't correct
35	Correct	38 ms	11320 KB	Output is correct
36	Incorrect	16 ms	11320 KB	Output isn't correct
37	Incorrect	18 ms	11320 KB	Output isn't correct
38	Correct	42 ms	11320 KB	Output is correct
39	Incorrect	19 ms	11320 KB	Output isn't correct
40	Incorrect	24 ms	11320 KB	Output isn't correct
41	Correct	70 ms	11320 KB	Output is correct
42	Incorrect	32 ms	11320 KB	Output isn't correct
43	Incorrect	21 ms	11320 KB	Output isn't correct
44	Correct	65 ms	11320 KB	Output is correct
45	Incorrect	32 ms	11320 KB	Output isn't correct
46	Incorrect	33 ms	11320 KB	Output isn't correct
47	Correct	122 ms	11320 KB	Output is correct
48	Incorrect	40 ms	11320 KB	Output isn't correct
49	Incorrect	31 ms	11320 KB	Output isn't correct
50	Correct	134 ms	11576 KB	Output is correct
51	Incorrect	42 ms	11860 KB	Output isn't correct
52	Incorrect	37 ms	12276 KB	Output isn't correct
53	Correct	149 ms	13460 KB	Output is correct
54	Incorrect	42 ms	13760 KB	Output isn't correct
55	Incorrect	60 ms	14228 KB	Output isn't correct
56	Correct	182 ms	15732 KB	Output is correct
57	Incorrect	67 ms	15828 KB	Output isn't correct
58	Incorrect	54 ms	16436 KB	Output isn't correct
59	Correct	207 ms	18020 KB	Output is correct
60	Incorrect	85 ms	18180 KB	Output isn't correct
61	Incorrect	46 ms	18768 KB	Output isn't correct
62	Correct	230 ms	20772 KB	Output is correct
63	Correct	168 ms	20772 KB	Output is correct
64	Correct	254 ms	21256 KB	Output is correct
65	Correct	263 ms	21796 KB	Output is correct
66	Correct	221 ms	22552 KB	Output is correct
67	Incorrect	200 ms	23052 KB	Output isn't correct
68	Correct	115 ms	23796 KB	Output is correct
69	Correct	149 ms	24324 KB	Output is correct
70	Correct	100 ms	24952 KB	Output is correct
71	Correct	98 ms	25712 KB	Output is correct
72	Correct	104 ms	26208 KB	Output is correct
73	Correct	102 ms	28864 KB	Output is correct
74	Correct	136 ms	29584 KB	Output is correct
75	Correct	108 ms	30168 KB	Output is correct
76	Correct	131 ms	30800 KB	Output is correct
77	Correct	134 ms	31540 KB	Output is correct
78	Incorrect	189 ms	32032 KB	Output isn't correct
79	Correct	108 ms	32716 KB	Output is correct
80	Correct	118 ms	33424 KB	Output is correct
81	Correct	150 ms	34044 KB	Output is correct
82	Correct	126 ms	34696 KB	Output is correct
83	Correct	153 ms	35124 KB	Output is correct
84	Correct	158 ms	35756 KB	Output is correct
85	Correct	141 ms	36452 KB	Output is correct
86	Correct	148 ms	37156 KB	Output is correct
87	Correct	184 ms	37708 KB	Output is correct
88	Correct	162 ms	38432 KB	Output is correct
89	Correct	147 ms	38964 KB	Output is correct
90	Correct	177 ms	39592 KB	Output is correct
91	Correct	136 ms	40220 KB	Output is correct
92	Correct	145 ms	40872 KB	Output is correct