답안 #117595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117595	2019-06-16T18:06:31 Z	KieranHorgan	Mecho (IOI09_mecho)	C++17	0 / 100	18 ms	7424 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

#	결과	실행 시간	메모리	Grader output
1	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	7 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	7 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	7 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	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	7 ms	5604 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	5496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	7 ms	5504 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	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	8 ms	5632 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	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	7 ms	5604 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	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	7 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	7 ms	5632 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	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	7 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	8 ms	5760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	13 ms	6244 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	10 ms	6144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	10 ms	6272 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	10 ms	6272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	11 ms	6528 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	11 ms	6396 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	12 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	11 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	12 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	12 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	12 ms	6628 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	12 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	13 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	13 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	13 ms	6656 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	18 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	13 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	14 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	14 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	14 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	15 ms	6784 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	14 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	17 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	16 ms	6980 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	15 ms	7168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	17 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	17 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	16 ms	7032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	15 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	15 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	16 ms	7168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	16 ms	7068 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	16 ms	7036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	16 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	15 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	15 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	15 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	15 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	15 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	17 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	17 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	17 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	18 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	16 ms	7012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	16 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	16 ms	7044 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	16 ms	7424 KB	Execution killed with signal 11 (could be triggered by violating memory limits)