oj.uz

Submission #124684

# Submission time Handle Problem Language Result Execution time Memory
124684 2019-07-03T17:17:59 Z arthurconmy Mecho (IOI09_mecho) C++14
10 / 100
 1000 ms 14156 KB 
// 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

	REP(i,0,n*n)
	{
		REP(i,0,801)
		{
			REP(j,0,801)
			{
				vis[i][j]=0;
			}
		}

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

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

		if(!try_it(i))
		{
			cout << i-1 << endl;
			return 0;
		}
	}

	// 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;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:167:6: warning: unused variable 'l' [-Wunused-variable]
  int l=0;
      ^
mecho.cpp:168:6: warning: unused variable 'r' [-Wunused-variable]
  int r=n*n; // bin search parameters
      ^

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3452 KB Output isn't correct
2 Incorrect 6 ms 3444 KB Output isn't correct
3 Incorrect 6 ms 3448 KB Output isn't correct
4 Incorrect 6 ms 3448 KB Output isn't correct
5 Correct 5 ms 3576 KB Output is correct
6 Correct 6 ms 3580 KB Output is correct
7 Incorrect 72 ms 7140 KB Output isn't correct
8 Correct 5 ms 3448 KB Output is correct
9 Incorrect 5 ms 3448 KB Output isn't correct
10 Incorrect 5 ms 3576 KB Output isn't correct
11 Incorrect 5 ms 3448 KB Output isn't correct
12 Execution timed out 1089 ms 3704 KB Time limit exceeded
13 Incorrect 5 ms 3576 KB Output isn't correct
14 Correct 6 ms 3704 KB Output is correct
15 Incorrect 59 ms 3576 KB Output isn't correct
16 Incorrect 5 ms 3576 KB Output isn't correct
17 Incorrect 96 ms 3624 KB Output isn't correct
18 Incorrect 5 ms 3576 KB Output isn't correct
19 Incorrect 134 ms 3616 KB Output isn't correct
20 Incorrect 5 ms 3576 KB Output isn't correct
21 Incorrect 240 ms 3644 KB Output isn't correct
22 Incorrect 8 ms 3576 KB Output isn't correct
23 Incorrect 379 ms 3676 KB Output isn't correct
24 Incorrect 5 ms 3576 KB Output isn't correct
25 Incorrect 545 ms 3704 KB Output isn't correct
26 Incorrect 5 ms 3704 KB Output isn't correct
27 Incorrect 651 ms 3724 KB Output isn't correct
28 Incorrect 6 ms 3704 KB Output isn't correct
29 Incorrect 745 ms 3736 KB Output isn't correct
30 Incorrect 5 ms 3704 KB Output isn't correct
31 Incorrect 870 ms 3756 KB Output isn't correct
32 Incorrect 6 ms 3708 KB Output isn't correct
33 Execution timed out 1086 ms 4600 KB Time limit exceeded
34 Incorrect 20 ms 4728 KB Output isn't correct
35 Incorrect 19 ms 4728 KB Output isn't correct
36 Execution timed out 1078 ms 4908 KB Time limit exceeded
37 Incorrect 25 ms 4856 KB Output isn't correct
38 Incorrect 24 ms 4856 KB Output isn't correct
39 Execution timed out 1082 ms 5112 KB Time limit exceeded
40 Incorrect 30 ms 5112 KB Output isn't correct
41 Incorrect 28 ms 5116 KB Output isn't correct
42 Execution timed out 1075 ms 5240 KB Time limit exceeded
43 Incorrect 36 ms 5220 KB Output isn't correct
44 Incorrect 32 ms 5240 KB Output isn't correct
45 Execution timed out 1069 ms 5456 KB Time limit exceeded
46 Incorrect 46 ms 5496 KB Output isn't correct
47 Incorrect 42 ms 5484 KB Output isn't correct
48 Execution timed out 1084 ms 5624 KB Time limit exceeded
49 Incorrect 48 ms 5752 KB Output isn't correct
50 Incorrect 47 ms 5752 KB Output isn't correct
51 Execution timed out 1076 ms 5880 KB Time limit exceeded
52 Incorrect 57 ms 5880 KB Output isn't correct
53 Incorrect 55 ms 6136 KB Output isn't correct
54 Execution timed out 1075 ms 6136 KB Time limit exceeded
55 Incorrect 64 ms 6136 KB Output isn't correct
56 Incorrect 58 ms 6136 KB Output isn't correct
57 Execution timed out 1067 ms 6392 KB Time limit exceeded
58 Incorrect 73 ms 6392 KB Output isn't correct
59 Incorrect 67 ms 6392 KB Output isn't correct
60 Execution timed out 1067 ms 6520 KB Time limit exceeded
61 Incorrect 81 ms 6648 KB Output isn't correct
62 Incorrect 84 ms 6776 KB Output isn't correct
63 Incorrect 75 ms 6648 KB Output isn't correct
64 Incorrect 75 ms 6648 KB Output isn't correct
65 Incorrect 76 ms 6652 KB Output isn't correct
66 Incorrect 76 ms 6632 KB Output isn't correct
67 Correct 76 ms 6648 KB Output is correct
68 Incorrect 76 ms 6744 KB Output isn't correct
69 Incorrect 77 ms 6672 KB Output isn't correct
70 Incorrect 77 ms 6676 KB Output isn't correct
71 Incorrect 77 ms 6744 KB Output isn't correct
72 Incorrect 76 ms 6776 KB Output isn't correct
73 Incorrect 73 ms 7716 KB Output isn't correct
74 Incorrect 72 ms 7712 KB Output isn't correct
75 Incorrect 72 ms 7704 KB Output isn't correct
76 Incorrect 72 ms 7708 KB Output isn't correct
77 Incorrect 75 ms 7704 KB Output isn't correct
78 Correct 70 ms 7568 KB Output is correct
79 Incorrect 70 ms 7384 KB Output isn't correct
80 Incorrect 71 ms 7516 KB Output isn't correct
81 Incorrect 70 ms 7384 KB Output isn't correct
82 Incorrect 70 ms 7384 KB Output isn't correct
83 Runtime error 79 ms 13900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 82 ms 14156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 82 ms 13992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 81 ms 13996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 80 ms 13856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Incorrect 72 ms 7416 KB Output isn't correct
89 Incorrect 71 ms 7288 KB Output isn't correct
90 Incorrect 71 ms 7260 KB Output isn't correct
91 Incorrect 72 ms 7368 KB Output isn't correct
92 Incorrect 71 ms 7412 KB Output isn't correct