Submission #124682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124682	2019-07-03T17:16:02 Z	arthurconmy	Mecho (IOI09_mecho)	C++14	4 / 100	1000 ms	14000 KB

mecho

// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define ff first
#define ss second
#define pb push_back
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)

int grid[802][802]; // 0: tree / boundary
					// 1: grass 
					// 2: hive
					// 3: mecho's home

int bee_dis[802][802];
int INF = int(1e9);
pii start;
int n,s;
bool vis[802][802];

bool try_it(int t)
{
	vector<pii> BFS = {start};

	int cur_dis=0;

	while(!BFS.empty())
	{
		// cout << cur_dis << endl;

		if(cur_dis%s == 0 && cur_dis!=0) t++;

		vector<pii> new_BFS;

		for(auto P:BFS)
		{
			REP(x,-1,1)
			{
				REP(y,-1,1)
				{
					// cout << P.ff+x << " " << P.ff+y << endl;

					if(vis[P.ff+x][P.ss+y]) continue;
					if(abs(x)+abs(y)!=1) continue;
					if(bee_dis[P.ff+x][P.ss+y] <= t) continue; // do we need to check that the current square isn't now bad?
						
					if(grid[P.ff+x][P.ss+y] == 3) return true;

					if(grid[P.ff+x][P.ss+y] != 1) continue;

					new_BFS.pb({P.ff+x,P.ss+y});
					vis[P.ff+x][P.ss+y]=1;
				}
			}

			BFS=new_BFS;
		}

		cur_dis++;
	}

	return false;
}

int main()
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	REP(i,0,801)
	{
		REP(j,0,801)
		{
			bee_dis[i][j]=INF;
		}
	}

	cin>>n>>s;

	vector<pii> bees;

	REP(i,1,n)
	{
		string row;
		cin>>row;

		REP(j,1,n)
		{
			if(row[j-1]=='G') grid[i][j]=1;
			if(row[j-1]=='H')
			{
				grid[i][j]=2;
				bees.pb({i,j});
				bee_dis[i][j]=0;
			}
			if(row[j-1]=='M')
			{
				grid[i][j]=1; // Mecho's start is grassy
				start={i,j};
			}
			if(row[j-1]=='D')
			{
				grid[i][j]=3;
			}
		}
	}

	// precompute bee_dis

	while(!bees.empty())
	{
		vector<pii> new_bees;

		for(auto b:bees)
		{
			REP(x,-1,1)
			{
				REP(y,-1,1)
				{
					if(abs(x)+abs(y)!=1) continue;
					if(bee_dis[b.ff+x][b.ss+y] != INF) continue;
					if(grid[b.ff+x][b.ss+y] != 1) continue;

					bee_dis[b.ff+x][b.ss+y]=1+bee_dis[b.ff][b.ss];
					new_bees.pb({b.ff+x,b.ss+y});
				}
			}
		}

		bees=new_bees;
	}

	// REP(i,1,n)
	// {
	// 	REP(j,1,n)
	// 	{
	// 		if(bee_dis[i][j]==INF)
	// 		{
	// 			cout << "-1 ";
	// 			continue;
	// 		}

	// 		cout << bee_dis[i][j] << " ";
	// 		if(bee_dis[i][j]<10) cout << " "; 
	// 	}
	// 	cout << endl;
	// }

	vis[start.ff][start.ss]=1;
	int l=0;
	int r=n*n; // bin search parameters

	while(l<=r)
	{
		REP(i,0,801)
		{
			REP(j,0,801)
			{
				vis[i][j]=0;
			}
		}

		// cout << l << " " << r << endl;

		vis[start.ff][start.ss]=1;

		int mid=(l+r)/2;

		if(try_it(mid))
		{
			l=mid;
		}

		else
		{
			r=mid-1;
		}
	}

	REP(i,0,801)
	{
		REP(j,0,801)
		{
			vis[i][j]=0;
		}
	}
	vis[start.ff][start.ss]=1;

	if(!try_it(0)) cout << -1 << endl;
	else cout << l << endl;
}

Subtask #1

4.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1082 ms	3448 KB	Time limit exceeded
2	Execution timed out	1064 ms	3448 KB	Time limit exceeded
3	Execution timed out	1049 ms	3448 KB	Time limit exceeded
4	Execution timed out	1073 ms	3448 KB	Time limit exceeded
5	Execution timed out	1069 ms	3448 KB	Time limit exceeded
6	Execution timed out	1040 ms	3448 KB	Time limit exceeded
7	Incorrect	81 ms	6868 KB	Output isn't correct
8	Correct	7 ms	3448 KB	Output is correct
9	Execution timed out	1058 ms	3448 KB	Time limit exceeded
10	Incorrect	8 ms	3452 KB	Output isn't correct
11	Execution timed out	1018 ms	3448 KB	Time limit exceeded
12	Execution timed out	1064 ms	3704 KB	Time limit exceeded
13	Incorrect	9 ms	3576 KB	Output isn't correct
14	Correct	9 ms	3708 KB	Output is correct
15	Execution timed out	1081 ms	3576 KB	Time limit exceeded
16	Incorrect	7 ms	3576 KB	Output isn't correct
17	Execution timed out	1070 ms	3576 KB	Time limit exceeded
18	Incorrect	8 ms	3576 KB	Output isn't correct
19	Execution timed out	1066 ms	3576 KB	Time limit exceeded
20	Incorrect	8 ms	3576 KB	Output isn't correct
21	Execution timed out	1068 ms	3576 KB	Time limit exceeded
22	Incorrect	9 ms	3580 KB	Output isn't correct
23	Execution timed out	1072 ms	3704 KB	Time limit exceeded
24	Incorrect	9 ms	3704 KB	Output isn't correct
25	Execution timed out	1084 ms	3704 KB	Time limit exceeded
26	Incorrect	9 ms	3704 KB	Output isn't correct
27	Execution timed out	1072 ms	3704 KB	Time limit exceeded
28	Incorrect	14 ms	3832 KB	Output isn't correct
29	Execution timed out	1083 ms	3704 KB	Time limit exceeded
30	Incorrect	11 ms	3704 KB	Output isn't correct
31	Execution timed out	1079 ms	3704 KB	Time limit exceeded
32	Incorrect	11 ms	3768 KB	Output isn't correct
33	Execution timed out	1067 ms	4600 KB	Time limit exceeded
34	Incorrect	57 ms	4728 KB	Output isn't correct
35	Incorrect	37 ms	4728 KB	Output isn't correct
36	Execution timed out	1070 ms	4856 KB	Time limit exceeded
37	Incorrect	75 ms	4920 KB	Output isn't correct
38	Incorrect	50 ms	5056 KB	Output isn't correct
39	Execution timed out	1078 ms	5112 KB	Time limit exceeded
40	Incorrect	93 ms	5128 KB	Output isn't correct
41	Incorrect	60 ms	5136 KB	Output isn't correct
42	Execution timed out	1064 ms	5208 KB	Time limit exceeded
43	Incorrect	113 ms	5368 KB	Output isn't correct
44	Incorrect	72 ms	5368 KB	Output isn't correct
45	Execution timed out	1080 ms	5496 KB	Time limit exceeded
46	Incorrect	141 ms	5496 KB	Output isn't correct
47	Incorrect	89 ms	5496 KB	Output isn't correct
48	Execution timed out	1068 ms	5628 KB	Time limit exceeded
49	Incorrect	167 ms	5752 KB	Output isn't correct
50	Incorrect	107 ms	5776 KB	Output isn't correct
51	Execution timed out	1070 ms	5876 KB	Time limit exceeded
52	Incorrect	197 ms	5964 KB	Output isn't correct
53	Incorrect	130 ms	6036 KB	Output isn't correct
54	Execution timed out	1070 ms	6136 KB	Time limit exceeded
55	Incorrect	224 ms	6200 KB	Output isn't correct
56	Incorrect	124 ms	6100 KB	Output isn't correct
57	Execution timed out	1071 ms	6392 KB	Time limit exceeded
58	Incorrect	266 ms	6416 KB	Output isn't correct
59	Incorrect	148 ms	6444 KB	Output isn't correct
60	Execution timed out	1064 ms	6520 KB	Time limit exceeded
61	Incorrect	300 ms	6776 KB	Output isn't correct
62	Incorrect	211 ms	6680 KB	Output isn't correct
63	Incorrect	82 ms	6648 KB	Output isn't correct
64	Incorrect	82 ms	6564 KB	Output isn't correct
65	Incorrect	82 ms	6648 KB	Output isn't correct
66	Incorrect	83 ms	6648 KB	Output isn't correct
67	Correct	82 ms	6648 KB	Output is correct
68	Incorrect	84 ms	6764 KB	Output isn't correct
69	Incorrect	83 ms	6776 KB	Output isn't correct
70	Incorrect	85 ms	6776 KB	Output isn't correct
71	Incorrect	85 ms	6784 KB	Output isn't correct
72	Incorrect	84 ms	6776 KB	Output isn't correct
73	Incorrect	81 ms	7812 KB	Output isn't correct
74	Incorrect	81 ms	7788 KB	Output isn't correct
75	Incorrect	81 ms	7804 KB	Output isn't correct
76	Incorrect	80 ms	7704 KB	Output isn't correct
77	Incorrect	82 ms	7800 KB	Output isn't correct
78	Correct	80 ms	7468 KB	Output is correct
79	Incorrect	82 ms	7400 KB	Output isn't correct
80	Incorrect	81 ms	7372 KB	Output isn't correct
81	Incorrect	80 ms	7384 KB	Output isn't correct
82	Incorrect	81 ms	7360 KB	Output isn't correct
83	Runtime error	82 ms	13956 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	84 ms	13896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	87 ms	13892 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	84 ms	14000 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	85 ms	14000 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Incorrect	80 ms	7288 KB	Output isn't correct
89	Incorrect	79 ms	7288 KB	Output isn't correct
90	Incorrect	84 ms	7288 KB	Output isn't correct
91	Incorrect	79 ms	7396 KB	Output isn't correct
92	Incorrect	81 ms	7280 KB	Output isn't correct