Submission #577241

#	Time	Username	Problem	Language	Result	Execution time	Memory
577241		dozer	T-Covering (eJOI19_covering)	C++14	100 / 100	318 ms	70900 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int modulo = 1e9 + 7; 

int32_t main()
{
	fastio();

	pii dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	pii dia[4] = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
	int n, m;
	cin>>n>>m;
	int arr[n + 5][m + 5], done[n + 5][m + 5];
	vector<pii> adj[n + 5][m + 5];
	memset(done , -1, sizeof(done));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cin>>arr[i][j], done[i][j] = 0;
	}
	int k;
	cin>>k;
	set<pii> spe;
	int ans = 0;
	for (int i = 1; i <= k; i++)
	{
		int x, y;
		cin>>x>>y;
		spe.insert({x + 1, y + 1});
		done[x + 1][y + 1] = 2;
		ans += arr[x + 1][y + 1];
	}
	//handle the ones that have only one way of placement
	vector<pii> tmp(spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		int cnt = 0, mini = modulo;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if (done[x + a][y + b] == 0) cnt++, mini = min(mini, arr[x + a][y + b]);
		}
		if (cnt < 3)
		{
			cout<<"No\n";
			return 0;
		}
		if (cnt == 3)
		{
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0) done[x + a][y + b] = 1, ans += arr[x + a][y + b];
			}
			done[x][y] = 1;
			spe.erase(i);
			continue;
		}
	}
	//handle the diagonals, which have only one way of placement
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		if (done[x][y] == 1) continue;
		int cnt = 0, mini = modulo;
		pii ne;
		for (int j = 0; j < 4; j++)
		{
			int a = dia[j].st, b = dia[j].nd;
			if (done[x + a][y + b] == 2) cnt++, ne = {a, b};
		}
		if (cnt > 1)
		{
			cout<<"No\n";
			return 0;
		}
		if (cnt == 1)
		{
			int c = ne.st, d = ne.nd;
			done[x][y] = 1;
			done[x + c][y + d] = 1;
			spe.erase({x, y});
			spe.erase({x + c, y + d});
			cnt = 0;
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0) cnt++, ans += arr[x + a][y + b], done[x + a][y + b] = 1;
			}
			if (done[x + 2 * c][y + d] == 0) cnt++, ans += arr[x + 2 * c][y + d], done[x + 2 * c][y + d] = 1;
			if (done[x + c][y + 2 * d] == 0) cnt++, ans += arr[x + c][y + 2 * d], done[x + c][y + 2 * d] = 1;
			if (cnt < 6) 
			{
				cout<<"No\n";
				return 0;
			}
		}
	}
	//handle the one that are left with one way of placement after placing the diagonals
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		int cnt = 0, mini = modulo;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if (done[x + a][y + b] == 0) cnt++, mini = min(mini, arr[x + a][y + b]);
		}
		if (cnt < 3)
		{
			cout<<"No\n";
			return 0;
		}
		if (cnt == 3)
		{
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0) done[x + a][y + b] = 1, ans += arr[x + a][y + b];
			}
			done[x][y] = 1;
			spe.erase(i);
			continue;
		}
	}
	//todo: handle the components which have one square between each other
	
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		for (int j = 0; j < 2; j++)
		{
			int a = dir[j].st * 2, b = dir[j].nd * 2;
			if (x + a < 0 || y + b < 0) continue;
			if (done[x + a][y + b] == 2) adj[x][y].pb({x + a, y + b}), adj[x + a][y + b].pb({x, y});
		}
		/*
		cout<<x<<sp<<y<<" : "<<endl;
		for (auto j : adj[x][y])
			cout<<j.st<<sp<<j.nd<<endl;
			*/
	}

	for (auto i : tmp)
	{
		int c = i.st, d = i.nd;
		if (done[c][d] == 1) continue;
		queue<pii> q;
		q.push({c, d});
		int mini = modulo, cnt = 0;
		long long tot = 0;
		int steps = 0;
		pii ne;
		while(!q.empty())
		{
			int x = q.front().st, y = q.front().nd;
			done[x][y] = 1;
			tot = tot + 1;
			//cout<<x<<sp<<y<<endl;
			spe.erase({x, y});
			q.pop();
			for (int j = 0; j < 4; j++)
			{
				int a = dir[j].st, b = dir[j].nd;
				if (done[x + a][y + b] == 0)
				{
					if (arr[x + a][y + b] < mini) ne = {x + a, y + b};
					cnt++, mini = min(mini, arr[x + a][y + b]);
					ans += arr[x + a][y + b];
					done[x + a][y + b] = 1;
				} 

			}
			for (int j = 0; j < adj[x][y].size(); j++)
			{
				int a = adj[x][y][j].st, b = adj[x][y][j].nd;
				if (done[a][b] != 1) q.push({a, b}), done[a][b] = 1; 
			}
		}
		if (cnt < tot * 3)
		{
			//cout<<cnt<<sp<<tot<<endl;
			cout<<"No\n";
			return 0;
		}
		if (cnt > tot * 3)
		{
			done[ne.st][ne.nd] = 0;
			ans -= arr[ne.st][ne.nd];
		}
	}
	//todo: choose the minimum ones
	tmp = vector<pii> (spe.begin(), spe.end());
	for (auto i : tmp)
	{
		int x = i.st, y = i.nd;
		int cnt = 0, mini = modulo;
		pii ne;
		for (int j = 0; j < 4; j++)
		{
			int a = dir[j].st, b = dir[j].nd;
			if (done[x + a][y + b] == 0)
			{
				if (mini > arr[x + a][y + b]) ne = {x + a, y + b};
				cnt++, mini = min(mini, arr[x + a][y + b]), ans += arr[x + a][y + b], done[x + a][y + b] = 1;
			}
		}
		if (cnt < 3)
		{
			cout<<"No\n";
			return 0;
		}
		done[x][y] = 1;
		spe.erase(i);
		if (cnt == 4)
		{
			done[ne.st][ne.nd] = 0;
			ans -= arr[ne.st][ne.nd];
		}
	}
	cout<<ans<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message (stderr)

covering.cpp: In function 'int32_t main()':
covering.cpp:80:16: warning: unused variable 'mini' [-Wunused-variable]
   80 |   int cnt = 0, mini = modulo;
      |                ^~~~
covering.cpp:191:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |    for (int j = 0; j < adj[x][y].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~
covering.cpp:169:7: warning: unused variable 'steps' [-Wunused-variable]
  169 |   int steps = 0;
      |       ^~~~~

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