Submission #286399

#	Time	Username	Problem	Language	Result	Execution time	Memory
286399		abyyskit	Mecho (IOI09_mecho)	C++14	100 / 100	377 ms	14836 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
#define x first
#define y second
int n;
int S;
struct spair{
	int x;
	int y;
};

bool inside(int a, int b){
	if ((a >= 0 && b >= 0) && (a < n && b < n)){
		return true;
	}
	return false;
}

struct node{
	char c;
	int d = -1;
	bool vis = false;
	spair sp = {-1, 0};
};

vector<vector<node>> g;
vector<pair<int, int>> D;
void bfs(vector<pair<int, int>> start){
	queue<pair<pair<int, int>, int>> q;
	FOR(i, 0, start.size()){
		q.push({start[i], 0});
	}
	while (!q.empty()){
		pair<pair<int, int>, int> tmp = q.front();
		q.pop();
		if (!g[tmp.x.x][tmp.x.y].vis){
			g[tmp.x.x][tmp.x.y].vis = true;
			g[tmp.x.x][tmp.x.y].d = tmp.y;
			FOR(i, 0, 4){
				int nx = tmp.x.x + D[i].x;
				int ny = tmp.x.y + D[i].y;
				if ((inside(nx, ny) &&!g[nx][ny].vis) &&
						(g[nx][ny].c != 'T' && g[nx][ny].c != 'D')){
					q.push({{nx, ny}, tmp.y + 1});
				}
			}
		}
	}
}

bool operator < (spair a, spair b){
	if (a.x == b.x){
		return a.y > b.y;
	}
	return a.x < b.x;
}

void fin_bfs(pair<int, int> end){
	priority_queue<pair<spair, pair<int, int>>> q;
	q.push({{INT_MAX - 1, 0}, end});
	while(!q.empty()){
		auto tmp = q.top();
		q.pop();
	//	cout << tmp.x.x << " " << tmp.x.y << "\n";
		if (g[tmp.y.x][tmp.y.y].sp < tmp.x){
		//	cout << "curent node: " << tmp.y.x << " " << tmp.y.y << "\n";
			g[tmp.y.x][tmp.y.y].sp = tmp.x;
			FOR(i, 0, 4){
				int nx = tmp.y.x + D[i].x;
				int ny = tmp.y.y + D[i].y;
				if (inside(nx, ny)&& g[nx][ny].c != 'T'){
					spair cur;
					cur.x = tmp.x.x;
					cur.y = tmp.x.y;
					cur.y++;
					if (cur.y > S){
						cur.y = 1;
						cur.x--;
					}
					if (cur.x > g[nx][ny].d){
						cur.x = g[nx][ny].d;
						cur.y = 1;
					}
					if (g[nx][ny].sp < cur){
						q.push({cur, {nx, ny}});
					}
				}	
			}
		}
	}
	
}


int main(){
	D = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	cin >> n >> S;
	g.resize(n, vector<node>(n));
	vector<pair<int, int>> start;
	pair<int, int> end;
	pair<int, int> s;
	FOR(i, 0, n){
		FOR(j, 0, n){
			cin >> g[i][j].c;
			if(g[i][j].c == 'H'){
				start.pb({i, j});
			}
			if (g[i][j].c == 'D'){
				end.x = i;
				end.y = j;		
			}
			if (g[i][j].c == 'M'){
				s = {i, j};
			}
		}
	}
	bfs(start);
/*	FOR(i, 0, g.size()){
		FOR(j, 0, g[i].size()){
			cout << g[i][j].d << " ";
		}
		cout << "\n";
	}*/
	fin_bfs(end);
	/*FOR(i, 0, g.size()){
		FOR(j, 0, g[i].size()){
			cout << "(" << g[i][j].sp.x << ", " << g[i][j].sp.y << ") ";
		}
		cout << "\n";
	}*/
	if (g[s.x][s.y].sp.x == -1){
		cout << "-1\n";
	}
	else{
		cout << g[s.x][s.y].sp.x - 1 << "\n";
	}

}

Compilation message (stderr)

mecho.cpp: In function 'void bfs(std::vector<std::pair<int, int> >)':
mecho.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   32 |  FOR(i, 0, start.size()){
      |      ~~~~~~~~~~~~~~~~~~                
mecho.cpp:32:2: note: in expansion of macro 'FOR'
   32 |  FOR(i, 0, start.size()){
      |  ^~~

• Subtask 1: 100 / 100