Submission #897084

#	Time	Username	Problem	Language	Result	Execution time	Memory
897084		Jawad_Akbar_JJ	T-Covering (eJOI19_covering)	C++17	15 / 100	9 ms	31068 KiB

covering

#include <iostream>
#include <vector>
#include <set>


using namespace std;

#define int long long

const int N = (1<<20) + 1;
vector<int> nei[N];
int n,m,k;
int r[N];
int c[N];
int Seen[N];

vector<vector<int>> seen,g;

bool valid(int i,int j){
	return (i>=1 and j>=1 and i<=n and j<=m);
}
vector<pair<int,int>> v = {{-1,-1},{-1,1},{1,-1},{1,1},{-2,0},{2,0},{0,2},{0,-2}},vvv = {{0,0},{0,1},{0,-1},{1,0},{-1,0}};



void make_graph(){

	for (int i=1;i<=k;i++){
		for (auto [a,b] : v){
			int nr = r[i] + a;
			int nc = c[i] + b;
			if (valid(nr,nc) and seen[nr][nc]!=0){
				nei[i].push_back(seen[nr][nc]);
				nei[seen[nr][nc]].push_back(i);
			}
		}
	}
}

set<vector<int>> s;
int sz = 0;
int sum = 0;
int Mn;

void dfs(int i){
	// cout<<i<<endl;
	Seen[i] = true;
	sz++;


	for (auto [a,b] : vvv){
		int nr = r[i] + a;
		int nc = c[i] + b;
		if (!valid(nr,nc) or s.find({nr,nc})!=s.end())
			continue;
		Mn = min(Mn,g[nr][nc]);
		sum += g[nr][nc];
		// cout<<"added "<<g[nr][nc]<<endl;
		s.insert({nr,nc});
	}

	
	for (int u : nei[i])
		if (!Seen[u])
			dfs(u);

}

signed main(){
	cin>>n>>m;

	g.resize(n+5,vector<int> (m+5,0));
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			cin>>g[i][j];		
			// cout<<i<<" "<<j<<endl;	
		}
		
	cin>>k;
	
	seen.resize(n+5,vector<int> (m+5,0));
	for (int i=1;i<=k;i++){
		cin>>r[i]>>c[i];
		r[i]++;
		c[i]++;
		seen[r[i]][c[i]] = i;
	}

	make_graph();

	int ans = 0;

	for (int i=1;i<=k;i++){
		if (!Seen[i]){
			s.clear();
			Mn = 10005;
			sum = 0;
			sz = 0;
			dfs(i);
			if (s.size()<4*sz){
				// for (auto q : s)
				// 	cout<<q[0]<<" "<<q[1]<<endl;
				cout<<"No"<<endl;
				return 0;
			}
			ans += sum;
			if (s.size() > 4 * sz){
				ans -= Mn;
				// cout<<"removed Mn == "<<Mn<<endl;
			}
		}
	}
	cout<<ans<<endl;

}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:100:16: warning: comparison of integer expressions of different signedness: 'std::set<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  100 |    if (s.size()<4*sz){
      |        ~~~~~~~~^~~~~
covering.cpp:107:17: warning: comparison of integer expressions of different signedness: 'std::set<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  107 |    if (s.size() > 4 * sz){
      |        ~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30