Submission #833875

#	Time	Username	Problem	Language	Result	Execution time	Memory
833875		tolbi	T-Covering (eJOI19_covering)	C++17	25 / 100	166 ms	12020 KiB

covering

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
#define tol(bi) (1LL<<((int)(bi)))
int main(){
	int h,w;
	cin>>h>>w;
	vector<vector<int>> val(h,vector<int>(w));
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; j++){
			cin>>val[i][j];
		}
	}
	int n;cin>>n;
	vector<vector<int>> arr(h,vector<int>(w,0));
	vector<pair<int,int>> spec(n); 
	for (int i = 0; i < n; i++){
		int x,y;cin>>x>>y;
		arr[x][y]=i+1;
		spec[i]={x,y};
	}
	vector<bool> vis(n,false);
	int ans=0;
	function<int(int)> dfs;
	function<int(int,int)> dallan;
	vector<int> crvis(n,false);
	dallan = [&](int x, int y)->int{
		int rval = 0;
		if (x>0 && arr[x-1][y]>0) {
			int rr = dfs(arr[x-1][y]-1);
			if (rr==-1) return -1;
			rval+=rr;
		}
		if (x+1<h && arr[x+1][y]>0) {
			int rr = dfs(arr[x+1][y]-1);
			if (rr==-1) return -1;
			rval+=rr;
		}
		if (y>0 && arr[x][y-1]>0) {
			int rr = dfs(arr[x][y-1]-1);
			if (rr==-1) return -1;
			rval+=rr;
		}
		if (y+1<w && arr[x][y+1]>0) {
			int rr = dfs(arr[x][y+1]-1);
			if (rr==-1) return -1;
			rval+=rr;
		}
		return rval;
	};
	dfs = [&](int node)->int{
		vis[node]=true;
		if (crvis[node]) return 0;
		crvis[node]=true;
		int x = spec[node].first;
		int y = spec[node].second;
		vector<pair<int,int>> ava;
		if (x>0 && arr[x-1][y]==0) ava.push_back({x-1,y});
		if (y>0 && arr[x][y-1]==0) ava.push_back({x,y-1});
		if (x+1<h && arr[x+1][y]==0) ava.push_back({x+1,y});
		if (y+1<w && arr[x][y+1]==0) ava.push_back({x,y+1});
		if (ava.size()<3){
			crvis[node]=false;
			return -1;
		}
		int rval = -1;
		for (int i = 0; i <= ava.size(); i++){
			int cnt = 0;
			for (int j = 0; j < ava.size(); j++){
				if (i==j) continue;
				cnt++;
			}
			if (cnt!=3) continue;
			int crr = 0;
			for (int j = 0; j < ava.size(); j++){
				if (i==j) continue;
				arr[ava[j].first][ava[j].second]=-23;
				crr+=val[ava[j].first][ava[j].second];
			}
			for (int j = 0; j < ava.size() && crr!=-1; j++){
				if (i==j) continue;
				int crrr = dallan(ava[j].first,ava[j].second);
				if (crrr==-1) crr=-1;
				else{
					crr+=crrr;
				}
			}
			for (int j = 0; j < ava.size(); j++){
				if (i==j) continue;
				arr[ava[j].first][ava[j].second]=0;
			}
			if (crr!=-1) rval=max(rval,crr);
		}
		crvis[node]=false;
		if (rval==-1) return rval;
		return rval+val[x][y];
	};
	for (int i = 0; i < n; i++){
		if (vis[i]) continue;
		int rval = dfs(i);
		if (rval==-1){
			ans=-1;
			break;
		}
		else {
			ans+=rval;
		}
	}
	if (ans==-1){
		cout<<"No"<<endl;
	}
	else cout<<ans<<endl;
}

Compilation message (stderr)

covering.cpp: In lambda function:
covering.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i = 0; i <= ava.size(); i++){
      |                   ~~^~~~~~~~~~~~~
covering.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for (int j = 0; j < ava.size(); j++){
      |                    ~~^~~~~~~~~~~~
covering.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for (int j = 0; j < ava.size(); j++){
      |                    ~~^~~~~~~~~~~~
covering.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for (int j = 0; j < ava.size() && crr!=-1; j++){
      |                    ~~^~~~~~~~~~~~
covering.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for (int j = 0; j < ava.size(); j++){
      |                    ~~^~~~~~~~~~~~

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