Submission #117593

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
117593	2019-06-16T18:04:22 Z	KieranHorgan	Mecho (IOI09_mecho)	C++17	0 / 100	37 ms	12672 KB

mecho

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 1000000007;

char grid[805][805];
int dist1[805][805];
pair<int,int> dist3[805][805];
int dist2[805][805];
int dist[805][805];
int vis[805][805];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long seed;
	asm("rdtsc" : "=A"(seed));
	srand(seed);

	int n, s;
	cin >> n >> s;
	int si, sj;
	int fi, fj;
	vector<pair<int,int>> p;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> grid[i][j];
			if(grid[i][j]=='J') {
				si = i;
				sj = j;
			}
			if(grid[i][j]=='H') {
				fi = i;
				fj = j;
			}
			if(grid[i][j]=='P') {
				p.push_back({i,j});
			}
			if(grid[i][j]=='B') grid[i][j]=0;
		}
	}

	vector<int> di = {1,0,-1,0};
	vector<int> dj = {0,1,0,-1};

	queue<pair<int,pair<int,int>>> q;

	memset(dist1,-1,sizeof(dist1));
	dist1[si][sj]=0;
	q.push({0,{si,sj}});
	while(!q.empty()) {
		int d = q.front().first;
		int i = q.front().second.first;
		int j = q.front().second.second;
		q.pop();
		for(int x = 0; x < 4; x++) {
			if(grid[i+di[x]][j+dj[x]] == 0) continue;
			if(dist1[i+di[x]][j+dj[x]] != -1) continue;
			dist1[i+di[x]][j+dj[x]] = d+1;
			q.push({d+1,{i+di[x],j+dj[x]}});
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(dist1[i][j]>0) {
				dist3[i][j] = {(dist1[i][j]+s-1)/s,(dist1[i][j]+s-1)%s};
			}



	memset(dist2,-1,sizeof(dist2));
	for(auto pp: p) {
		int pi = pp.first;
		int pj = pp.second;
		dist2[pi][pj]=0;
		q.push({0,{pi,pj}});
	}
	while(!q.empty()) {
		int d = q.front().first;
		int i = q.front().second.first;
		int j = q.front().second.second;
		q.pop();
		for(int x = 0; x < 4; x++) {
			if(grid[i+di[x]][j+dj[x]] == 0) continue;
			if(dist2[i+di[x]][j+dj[x]] != -1) continue;
			if(grid[i+di[x]][j+dj[x]] == 'H') continue;
			dist2[i+di[x]][j+dj[x]] = d+1;
			q.push({d+1,{i+di[x],j+dj[x]}});
		}
	}


	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(dist1[i][j]>=0) {
				dist[i][j] = dist2[i][j]-dist3[i][j].first-(dist3[i][j].second==s-1);
			}

	// for(int i = 1; i <= n; i++) {
		// for(int j = 1; j <= n; j++) {
			// cerr << dist3[i][j].first << ":" << dist3[i][j].second << " ";
		// }
		// cerr << endl;
	// }
	// cerr << endl;
	// for(int i = 1; i <= n; i++) {
		// for(int j = 1; j <= n; j++) {
			// cerr << dist2[i][j] << " ";
		// }
		// cerr << endl;
	// }
	// cerr << endl;
	// for(int i = 1; i <= n; i++) {
		// for(int j = 1; j <= n; j++) {
			// cerr << dist[i][j] << " ";
		// }
		// cerr << endl;
	// }
	// cerr << endl;

	priority_queue<pair<int,pair<int,int>>> pq;
	pq.push({dist[si][sj], {si, sj}});
	int ans = dist[si][sj];
	bool toBreak = 0;
	while(!pq.empty()) {
		int d = pq.top().first;
		int i = pq.top().second.first;
		int j = pq.top().second.second;
		pq.pop();
		ans = min(ans, d);
		if(i==fi && j == fj) break;
		for(int x = 0; x < 4; x++) {
			if(grid[i+di[x]][j+dj[x]] == 'H') {toBreak = 1; break;}
			if(grid[i+di[x]][j+dj[x]] == 0) continue;
			if(dist1[i+di[x]][j+dj[x]] <= 0) continue;
			if(vis[i+di[x]][j+dj[x]]) continue;
			vis[i+di[x]][j+dj[x]] = 1;
			pq.push({dist[i+di[x]][j+dj[x]],{i+di[x],j+dj[x]}});
		}
		if(toBreak)break;
	}
	cout << ans << endl;
}

Compilation message

mecho.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
mecho.cpp: In function 'int main()':
mecho.cpp:141:17: warning: 'fj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i==fi && j == fj) break;
               ~~^~~~~
mecho.cpp:141:7: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i==fi && j == fj) break;
      ~^~~~

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	14 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	13 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	14 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	13 ms	10724 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	13 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	13 ms	10724 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	24 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	12 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	14 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	12 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	12 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	12 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	12 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	12 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	13 ms	10624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	13 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	14 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	18 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
26	Runtime error	13 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	13 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	12 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	13 ms	10880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	13 ms	10752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	13 ms	10880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	14 ms	10776 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	15 ms	11264 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	15 ms	11264 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	14 ms	11392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	15 ms	11512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	15 ms	11520 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	16 ms	11392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	16 ms	11648 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	16 ms	11592 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	16 ms	11648 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	16 ms	11696 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	30 ms	11648 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	16 ms	11844 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	19 ms	11808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	17 ms	11904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	17 ms	11776 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	18 ms	11904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	17 ms	11904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	18 ms	12032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	18 ms	12160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	19 ms	12160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	18 ms	12132 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	19 ms	12288 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	19 ms	12160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	19 ms	12288 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	20 ms	12408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	19 ms	12416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	20 ms	12416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	20 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	20 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	20 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	20 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	20 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	20 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	21 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	21 ms	12668 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	21 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	21 ms	12516 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	21 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	21 ms	12552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	21 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	20 ms	12664 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	21 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	20 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	20 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	20 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	21 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	20 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	20 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	20 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	20 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	20 ms	12616 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	21 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	21 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	37 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	21 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	20 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	25 ms	12672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	21 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	21 ms	12536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	21 ms	12544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)