ECAPR209 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Sandeep SIngh

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

bfs, priority-queue

QUICK EXPLANATION

Sort the queries in ascending order and solve them offline. Make use of the fact that after sorting, a ninja will kill all the monsters that were killed by the previous ninja so no need to start again. For finding how many monsters will be killed by a ninja, do a bfs using priority queue.

EXPLANATION:

Notice that the start position is the same for each query. Thus, if we sort the queries in ascending order, monsters killed in a query will also be killed by the next query. So rather than recalculating again, we can start from the point where the previous query stopped.

Monsters killed in a query can be found by simple bfs using priority queue. For each monster killed, we add the adjacent monsters to the queue. We do this till the ninja is able to kill monsters.

Thus we answer all the queries.
Refer to the solution for implementation.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 1005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
int arr[MAX][MAX];
bool vis[MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int soln[200005];
 
 
 
void solve(){
	
	int n ,i ,j ,h ,w, q;
	cin >> n >> q;
	memset(vis,0,sizeof(vis));
 
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++)
			cin >> arr[i][j];
	}
	
	int p;
	vector<pair<int,int>> queries;
	for(i=0; i<q; i++){
		cin >> p;
		queries.push_back( {p, i} );
	}	
 
	sort(queries.begin(),queries.end());
 
	priority_queue <pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
 
	pq.push({arr[1][1], {1,1} });
	vis[1][1] = 1; 
	int ans=0, ni, nj;
 
	for(auto x: queries){
		
		while(!(pq.empty()) && x.first > pq.top().first){
 
			++ans;
			auto tmp = pq.top().second;
			pq.pop();			
 
			for(i=0; i<4 ;i++){
				ni = tmp.first + dx[i];
				nj = tmp.second + dy[i];
				if( (ni>0 && ni<=n) && (nj>0 && nj<=n) && !(vis[ni][nj]))
					pq.push( {arr[ni][nj], {ni, nj}} ),vis[ni][nj] = 1;
			}
			
		}
		soln[x.second] = ans;
	}
 
	for(i=0; i<q; i++)
		cout<<soln[i]<<endl;
}
int main(){
	FAST;
	
	int t;
	cin>>t;
	while(t--)
		solve();
}
4 Likes