oj.uz

답안 #138843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138843 2019-07-30T13:14:35 Z StevenH Mecho (IOI09_mecho) C++14
9 / 100
 1000 ms 65540 KB 
#include <iostream>
#include <fstream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int _map[805][805];
int map[805][805];
int n,s;
struct Node{
	int x,y,tm;
};
void print()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			printf("%c",map[i][j]);
		printf("\n");
	}
}
void run(int t)
{
	for(int i=0;i<t;i++)
	{
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				if(map[j][k]=='H')
				{
					if(j+1< n && map[j+1][k]=='G')map[j+1][k]='K';
					if(j-1>=0 && map[j-1][k]=='G')map[j-1][k]='K';
					if(k+1< n && map[j][k+1]=='G')map[j][k+1]='K';
					if(k-1>=0 && map[j][k-1]=='G')map[j][k-1]='K';
				}
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				if(map[j][k]=='K')
					map[j][k]='H';
	}

}
void copy()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			map[i][j]=_map[i][j];
}
bool f[805][805];
bool vis[805][805];
int ss[2000000][2];
int k;
bool judge(int x,int y)
{
	if(x<0 || y<0 || x>=n || y>=n)return 0;
	if(vis[x][y])return 0;
	if(map[x][y]=='T')return 0;
	if(map[x][y]=='H')return 0;
	return 1;

}
int flag;
void dfs(int x,int y,int p)
{
	//printf("%d %d\n",x,y);
	f[x][y]=1;
	if(flag)return;
	if(map[x][y]=='D')
	{
		//printf("%d\n",p);
		k=1;
		ss[0][0]=x;
		ss[0][1]=y;
		flag=1;
		return;
	}
	if(p==s)
	{
		ss[k][0]=x;
		ss[k][1]=y;
		k++;
		f[x][y]=0;
		return;
	}
	if(judge(x+1,y))dfs(x+1,y,p+1);
	if(judge(x-1,y))dfs(x-1,y,p+1);
	if(judge(x,y+1))dfs(x,y+1,p+1);
	if(judge(x,y-1))dfs(x,y-1,p+1);

}
bool bfs(int sx,int sy,int t)
{
	memset(vis,0,sizeof(vis));
	copy();
	run(t);
	queue<Node> que;
	que.push({sx,sy,0});
	vis[sx][sy]=1;
	int tm=0;
	while(!que.empty())
	{
		Node now=que.front();
		if(now.tm>tm)
			run(1),tm++;
		que.pop();
		k=0;
		memset(f,0,sizeof(f));
		flag=0;
		dfs(now.x,now.y,0);
		//if(k>0)printf("%d %d %d\n",now.x,now.y,k);
		for(int i=0;i<k;i++)
		{
			int x=ss[i][0];
			int y=ss[i][1];
			vis[x][y]=1;
			if(map[x][y]=='D')return 1;
			else que.push({x,y,now.tm+1});
		}
		//if(k>0)printf("\n");
	}
	return 0;

}
int main()
{
	//freopen("sample.in","rb",stdin);
	int sx,sy;
	scanf("%d%d",&n,&s);
	//printf("%d %d",n,s);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			char res;
			while(scanf("%c",&_map[i][j]))
				if(_map[i][j]>='A' && _map[i][j]<='Z')
					break;
			if(_map[i][j]=='M')
				sx=i,sy=j;
		}
	if(!bfs(sx,sy,0))printf("-1");
	else
	{
		if(!(sx,sy,1))printf("0");
		else 
		{
			int left=1,right=1;
			while(bfs(sx,sy,right))left=right,right*=2;
			if(right==1)printf("1");
			else
			{
				right--;
				//printf("%d*%d\n",left,right);
				while(left<right)
				{
					int mid=(left+right)/2;
					if((left+right)%2==1)mid++;
					if(bfs(sx,sy,mid))left=mid;
					else right=mid-1;
				}
				printf("%d",left);
			}
		}
	}

	return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:133:32: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
    while(scanf("%c",&_map[i][j]))
                     ~~~~~~~~~~~^
mecho.cpp:132:9: warning: unused variable 'res' [-Wunused-variable]
    char res;
         ^~~
mecho.cpp:142:11: warning: left operand of comma operator has no effect [-Wunused-value]
   if(!(sx,sy,1))printf("0");
           ^~
mecho.cpp:142:14: warning: right operand of comma operator has no effect [-Wunused-value]
   if(!(sx,sy,1))printf("0");
              ^
mecho.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&s);
  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:146:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
    while(bfs(sx,sy,right))left=right,right*=2;
          ~~~^~~~~~~~~~~~~
mecho.cpp:146:13: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
9.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1656 KB Output isn't correct
2 Incorrect 5 ms 1656 KB Output isn't correct
3 Incorrect 4 ms 1656 KB Output isn't correct
4 Incorrect 4 ms 1656 KB Output isn't correct
5 Incorrect 4 ms 1656 KB Output isn't correct
6 Correct 6 ms 1656 KB Output is correct
7 Runtime error 191 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 4 ms 1656 KB Output isn't correct
9 Execution timed out 1064 ms 3100 KB Time limit exceeded
10 Correct 8 ms 1784 KB Output is correct
11 Correct 20 ms 1660 KB Output is correct
12 Execution timed out 1061 ms 2040 KB Time limit exceeded
13 Incorrect 71 ms 1912 KB Output isn't correct
14 Correct 155 ms 2028 KB Output is correct
15 Incorrect 10 ms 1656 KB Output isn't correct
16 Correct 361 ms 1836 KB Output is correct
17 Incorrect 12 ms 1784 KB Output isn't correct
18 Execution timed out 1060 ms 2160 KB Time limit exceeded
19 Incorrect 21 ms 1784 KB Output isn't correct
20 Execution timed out 1067 ms 3576 KB Time limit exceeded
21 Incorrect 49 ms 1912 KB Output isn't correct
22 Runtime error 173 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Incorrect 133 ms 1952 KB Output isn't correct
24 Runtime error 133 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Incorrect 217 ms 2040 KB Output isn't correct
26 Runtime error 141 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Incorrect 410 ms 2048 KB Output isn't correct
28 Runtime error 129 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Incorrect 474 ms 2080 KB Output isn't correct
30 Runtime error 131 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Incorrect 585 ms 2112 KB Output isn't correct
32 Runtime error 136 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Execution timed out 1075 ms 3960 KB Time limit exceeded
34 Runtime error 133 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 127 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Execution timed out 1063 ms 4344 KB Time limit exceeded
37 Runtime error 152 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 127 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Execution timed out 1080 ms 4600 KB Time limit exceeded
40 Runtime error 140 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 137 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Execution timed out 1073 ms 4984 KB Time limit exceeded
43 Runtime error 142 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Runtime error 130 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Execution timed out 1053 ms 5368 KB Time limit exceeded
46 Runtime error 149 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 134 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Execution timed out 1053 ms 5672 KB Time limit exceeded
49 Runtime error 160 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Runtime error 146 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Execution timed out 1069 ms 6136 KB Time limit exceeded
52 Runtime error 217 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 144 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Execution timed out 1067 ms 6492 KB Time limit exceeded
55 Runtime error 152 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 141 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Execution timed out 1025 ms 6904 KB Time limit exceeded
58 Runtime error 156 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 158 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Execution timed out 1066 ms 7180 KB Time limit exceeded
61 Runtime error 169 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Runtime error 147 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Execution timed out 1076 ms 7308 KB Time limit exceeded
64 Runtime error 237 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Execution timed out 1078 ms 7288 KB Time limit exceeded
66 Execution timed out 1081 ms 7416 KB Time limit exceeded
67 Execution timed out 1081 ms 7300 KB Time limit exceeded
68 Runtime error 215 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 207 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Execution timed out 1085 ms 11196 KB Time limit exceeded
71 Execution timed out 1072 ms 7952 KB Time limit exceeded
72 Runtime error 210 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Execution timed out 1062 ms 8416 KB Time limit exceeded
74 Runtime error 134 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Execution timed out 1067 ms 10020 KB Time limit exceeded
76 Execution timed out 1063 ms 7564 KB Time limit exceeded
77 Runtime error 133 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Execution timed out 1069 ms 38920 KB Time limit exceeded
79 Runtime error 136 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Execution timed out 1035 ms 38912 KB Time limit exceeded
81 Execution timed out 1058 ms 8364 KB Time limit exceeded
82 Runtime error 133 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Execution timed out 1070 ms 45656 KB Time limit exceeded
84 Runtime error 204 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 190 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 192 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 192 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 192 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 214 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 203 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 191 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 191 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)