oj.uz

Submission #897084

# Submission time Handle Problem Language Result Execution time Memory
897084 2024-01-02T14:18:16 Z Jawad_Akbar_JJ T-Covering (eJOI19_covering) C++17
15 / 100
 9 ms 31068 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 31064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30812 KB Output is correct
2 Correct 7 ms 31064 KB Output is correct
3 Correct 6 ms 30808 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 6 ms 30812 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 31068 KB Output isn't correct
2 Halted 0 ms 0 KB -