oj.uz

Submission #124686

# Submission time Handle Problem Language Result Execution time Memory
124686 2019-07-03T17:19:13 Z arthurconmy Mecho (IOI09_mecho) C++14
28 / 100
 1000 ms 7836 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:166:6: warning: unused variable 'l' [-Wunused-variable]
  int l=0;
      ^
mecho.cpp:167:6: warning: unused variable 'r' [-Wunused-variable]
  int r=n*n; // bin search parameters
      ^

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3448 KB Output isn't correct
2 Incorrect 6 ms 3568 KB Output isn't correct
3 Incorrect 6 ms 3448 KB Output isn't correct
4 Incorrect 6 ms 3536 KB Output isn't correct
5 Correct 5 ms 3448 KB Output is correct
6 Correct 5 ms 3452 KB Output is correct
7 Correct 400 ms 7076 KB Output is correct
8 Incorrect 5 ms 3448 KB Output isn't correct
9 Correct 8 ms 3576 KB Output is correct
10 Correct 8 ms 3448 KB Output is correct
11 Correct 8 ms 3576 KB Output is correct
12 Execution timed out 1078 ms 3704 KB Time limit exceeded
13 Incorrect 6 ms 3576 KB Output isn't correct
14 Correct 5 ms 3704 KB Output is correct
15 Incorrect 60 ms 3576 KB Output isn't correct
16 Correct 30 ms 3576 KB Output is correct
17 Incorrect 96 ms 3576 KB Output isn't correct
18 Correct 46 ms 3576 KB Output is correct
19 Incorrect 133 ms 3704 KB Output isn't correct
20 Correct 64 ms 3604 KB Output is correct
21 Incorrect 239 ms 3576 KB Output isn't correct
22 Correct 122 ms 3676 KB Output is correct
23 Incorrect 378 ms 3672 KB Output isn't correct
24 Correct 186 ms 3704 KB Output is correct
25 Incorrect 545 ms 3832 KB Output isn't correct
26 Correct 280 ms 3704 KB Output is correct
27 Incorrect 651 ms 3804 KB Output isn't correct
28 Correct 331 ms 3704 KB Output is correct
29 Incorrect 749 ms 3768 KB Output isn't correct
30 Correct 378 ms 3832 KB Output is correct
31 Incorrect 873 ms 3832 KB Output isn't correct
32 Correct 439 ms 3832 KB Output is correct
33 Execution timed out 1077 ms 4728 KB Time limit exceeded
34 Execution timed out 1080 ms 4728 KB Time limit exceeded
35 Correct 36 ms 4856 KB Output is correct
36 Execution timed out 1077 ms 4856 KB Time limit exceeded
37 Execution timed out 1074 ms 4856 KB Time limit exceeded
38 Correct 43 ms 4856 KB Output is correct
39 Execution timed out 1074 ms 5112 KB Time limit exceeded
40 Execution timed out 1078 ms 5112 KB Time limit exceeded
41 Correct 55 ms 5112 KB Output is correct
42 Execution timed out 1075 ms 5240 KB Time limit exceeded
43 Execution timed out 1074 ms 5240 KB Time limit exceeded
44 Correct 67 ms 5244 KB Output is correct
45 Execution timed out 1087 ms 5504 KB Time limit exceeded
46 Execution timed out 1080 ms 5496 KB Time limit exceeded
47 Correct 83 ms 5496 KB Output is correct
48 Execution timed out 1089 ms 5628 KB Time limit exceeded
49 Execution timed out 1065 ms 5624 KB Time limit exceeded
50 Correct 100 ms 5752 KB Output is correct
51 Execution timed out 1073 ms 5880 KB Time limit exceeded
52 Execution timed out 1085 ms 5880 KB Time limit exceeded
53 Correct 117 ms 5880 KB Output is correct
54 Execution timed out 1079 ms 6140 KB Time limit exceeded
55 Execution timed out 1083 ms 6136 KB Time limit exceeded
56 Correct 130 ms 6136 KB Output is correct
57 Execution timed out 1075 ms 6396 KB Time limit exceeded
58 Execution timed out 1079 ms 6264 KB Time limit exceeded
59 Correct 162 ms 6392 KB Output is correct
60 Execution timed out 1083 ms 6520 KB Time limit exceeded
61 Execution timed out 1071 ms 6520 KB Time limit exceeded
62 Correct 179 ms 6648 KB Output is correct
63 Correct 121 ms 6432 KB Output is correct
64 Execution timed out 1071 ms 6520 KB Time limit exceeded
65 Execution timed out 1082 ms 6524 KB Time limit exceeded
66 Execution timed out 1071 ms 6520 KB Time limit exceeded
67 Correct 92 ms 6520 KB Output is correct
68 Correct 95 ms 6648 KB Output is correct
69 Correct 348 ms 6776 KB Output is correct
70 Correct 174 ms 6776 KB Output is correct
71 Correct 128 ms 6648 KB Output is correct
72 Incorrect 636 ms 6648 KB Output isn't correct
73 Incorrect 106 ms 7800 KB Output isn't correct
74 Execution timed out 1080 ms 7704 KB Time limit exceeded
75 Execution timed out 1054 ms 7712 KB Time limit exceeded
76 Correct 555 ms 7836 KB Output is correct
77 Execution timed out 1083 ms 7576 KB Time limit exceeded
78 Correct 82 ms 7384 KB Output is correct
79 Execution timed out 1072 ms 7260 KB Time limit exceeded
80 Correct 888 ms 7460 KB Output is correct
81 Correct 541 ms 7384 KB Output is correct
82 Execution timed out 1080 ms 7256 KB Time limit exceeded
83 Correct 97 ms 7336 KB Output is correct
84 Execution timed out 1083 ms 7132 KB Time limit exceeded
85 Correct 648 ms 7244 KB Output is correct
86 Correct 376 ms 7116 KB Output is correct
87 Correct 976 ms 7104 KB Output is correct
88 Correct 98 ms 7160 KB Output is correct
89 Correct 887 ms 7156 KB Output is correct
90 Correct 406 ms 7144 KB Output is correct
91 Correct 563 ms 7160 KB Output is correct
92 Correct 269 ms 7284 KB Output is correct