Submission #117594

#	Time	Username	Problem	Language	Result	Execution time	Memory
117594		KieranHorgan	Salesman (IOI09_salesman)	C++17	0 / 100	862 ms	10752 KiB

salesman

#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 (stderr)

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

• Subtask 1: 0 / 100