Submission #117598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
117598	2019-06-16T18:08:27 Z	KieranHorgan	Mecho (IOI09_mecho)	C++17	0 / 100	17 ms	7040 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 short
#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	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	7 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	15 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	7 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	7 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	7 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	7 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
26	Runtime error	7 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	7 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	7 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	7 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	6 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	9 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	9 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	9 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	10 ms	6272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	11 ms	6272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	9 ms	6272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	10 ms	6400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	11 ms	6400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	10 ms	6400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	10 ms	6400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	10 ms	6272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	10 ms	6272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	11 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	11 ms	6400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	11 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	12 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	12 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	11 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	13 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	13 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	13 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	13 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	14 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	13 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	14 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	14 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	15 ms	6884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	15 ms	6816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	16 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	15 ms	6884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	16 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	16 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	16 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	17 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)