Submission #1090885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090885		Muhammet	T-Covering (eJOI19_covering)	C++17	100 / 100	745 ms	74120 KiB

covering

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define sz(s) (int)s.size()

int n, m, k;

vector <vector <int>> a, b;

vector <pair<int,int>> v;

vector <vector<int>> vc;

map <pair<int,int>,int> vis, vis1;

map <int,int> vi;

vector <int> p, v2, v3;

int fnd(int x){
	if(p[x] == x) return x;
	return p[x] = fnd(p[x]);
}

void dfs(int x){
	vi[x] = 1;
	v2.push_back(x);
	for(auto i : vc[x]){
		if(vi.find(i) == vi.end()){
			dfs(i);
		}
	}
}

int main(){
	cin >> n >> m;
	a.assign(n+1, vector <int> (m+1,0));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	cin >> k;
	p.assign(k+1,0);
	v.assign(k+1,{0,0});
	for(int i = 0; i < k; i++){
		cin >> v[i].ff >> v[i].ss;
		v[i].ff++;
		v[i].ss++;
		vis[v[i]] = i;
		p[i] = i;
	}
	vector <int> v1;
	vc.resize(k+1);
	for(int i1 = 0; i1 < k; i1++){
		int x = v[i1].ff, y = v[i1].ss;
		for(int i = max(x-2,1); i <= min(x+2,n); i++){
			for(int j = max(y-2,1); j <= min(y+2,m); j++){
				if(abs(x-i) + abs(y-j) <= 2 and vis.find({i,j}) != vis.end()){
					int a1 = fnd(vis[{i,j}]), b1 = fnd(vis[{x,y}]);
					if(a1 != b1){
						vc[a1].push_back(b1);
						vc[b1].push_back(a1);
						p[a1] = b1;
					}
				}
			}
		}
	}
	long long int ans = 0;
	for(int i = 0; i < k; i++){
		if(vi.find(i) == vi.end()){
			v2.clear();
			dfs(i);
			v3.clear();
			for(auto j : v2){
				vis1[v[j]] = 1;
				ans += a[v[j].ff][v[j].ss];
			}
			for(auto j : v2){
				if(vis1.find({v[j].ff,v[j].ss+1}) == vis1.end() and v[j].ss+1 <= m){
					vis1[{v[j].ff,v[j].ss+1}] = 1;
					v3.push_back(a[v[j].ff][v[j].ss+1]);
					ans += a[v[j].ff][v[j].ss+1];
				}
				if(vis1.find({v[j].ff,v[j].ss-1}) == vis1.end() and v[j].ss-1 > 0){
					vis1[{v[j].ff,v[j].ss-1}] = 1;
					v3.push_back(a[v[j].ff][v[j].ss-1]);
					ans += a[v[j].ff][v[j].ss-1];
				}
				if(vis1.find({v[j].ff+1,v[j].ss}) == vis1.end() and v[j].ff+1 <= n){
					vis1[{v[j].ff+1,v[j].ss}] = 1;
					v3.push_back(a[v[j].ff+1][v[j].ss]);
					ans += a[v[j].ff+1][v[j].ss];
				}
				if(vis1.find({v[j].ff-1,v[j].ss}) == vis1.end() and v[j].ff-1 > 0){
					vis1[{v[j].ff-1,v[j].ss}] = 1;
					v3.push_back(a[v[j].ff-1][v[j].ss]);
					ans += a[v[j].ff-1][v[j].ss];
				}
			}
			sort(v3.begin(), v3.end());
			if(sz(v3) < 3*sz(v2)){
				cout << "No";
				return 0;
			}
			if(sz(v3) > 3*sz(v2)) ans -= v3[0];
		}
	}
	cout << ans;
}

• 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