답안 #834596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834596	2023-08-22T15:44:42 Z	tolbi	T-Covering (eJOI19_covering)	C++17	55 / 100	166 ms	19784 KB

covering

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tol(bi) (1LL<<((int)(bi)))
int32_t 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<void(int,int)> dallan;
	vector<int> crvis(n,false);
	set<int> st;
	dallan = [&](int x, int y)->void{
		if (x>0 && arr[x-1][y]>0) {
			st.insert(arr[x-1][y]-1);
		}
		if (x+1<h && arr[x+1][y]>0) {
			st.insert(arr[x+1][y]-1);
		}
		if (y>0 && arr[x][y-1]>0) {
			st.insert(arr[x][y-1]-1);
		}
		if (y+1<w && arr[x][y+1]>0) {
			st.insert(arr[x][y+1]-1);
		}
	};
	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;
		set<int> crset;
		if (x>0) dallan(x-1,y);
		if (y>0) dallan(x,y-1);
		if (x+1<h) dallan(x+1,y);
		if (y+1<w) dallan(x,y+1);
		dallan(x,y);
		swap(crset,st);
		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 (auto it : crset){
				int crrr=dfs(it);
				if (crrr==-1){
					crr=-1;
					break;
				}
				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

covering.cpp: In lambda function:
covering.cpp:66:21: 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]
   66 |   for (int i = 0; i <= ava.size(); i++){
      |                   ~~^~~~~~~~~~~~~
covering.cpp:68: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]
   68 |    for (int j = 0; j < ava.size(); j++){
      |                    ~~^~~~~~~~~~~~
covering.cpp:74: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]
   74 |    for (int j = 0; j < ava.size(); j++){
      |                    ~~^~~~~~~~~~~~
covering.cpp:89: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]
   89 |    for (int j = 0; j < ava.size(); j++){
      |                    ~~^~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	5 ms	852 KB	Output is correct
3	Correct	15 ms	2260 KB	Output is correct
4	Correct	43 ms	6104 KB	Output is correct
5	Correct	145 ms	19780 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	440 KB	Output is correct
2	Correct	5 ms	852 KB	Output is correct
3	Correct	19 ms	2260 KB	Output is correct
4	Correct	44 ms	6096 KB	Output is correct
5	Correct	166 ms	19780 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	5 ms	824 KB	Output is correct
3	Correct	15 ms	2216 KB	Output is correct
4	Correct	45 ms	6112 KB	Output is correct
5	Correct	144 ms	19784 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	8 ms	1216 KB	Output is correct
4	Correct	6 ms	820 KB	Output is correct
5	Correct	17 ms	2304 KB	Output is correct

Subtask #5

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	300 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	5 ms	852 KB	Output is correct
3	Correct	15 ms	2260 KB	Output is correct
4	Correct	43 ms	6104 KB	Output is correct
5	Correct	145 ms	19780 KB	Output is correct
6	Correct	2 ms	440 KB	Output is correct
7	Correct	5 ms	852 KB	Output is correct
8	Correct	19 ms	2260 KB	Output is correct
9	Correct	44 ms	6096 KB	Output is correct
10	Correct	166 ms	19780 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	5 ms	824 KB	Output is correct
13	Correct	15 ms	2216 KB	Output is correct
14	Correct	45 ms	6112 KB	Output is correct
15	Correct	144 ms	19784 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	8 ms	1216 KB	Output is correct
19	Correct	6 ms	820 KB	Output is correct
20	Correct	17 ms	2304 KB	Output is correct
21	Correct	2 ms	468 KB	Output is correct
22	Correct	5 ms	788 KB	Output is correct
23	Correct	21 ms	2232 KB	Output is correct
24	Correct	53 ms	6092 KB	Output is correct
25	Correct	145 ms	19784 KB	Output is correct

Subtask #7

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	5 ms	852 KB	Output is correct
3	Correct	15 ms	2260 KB	Output is correct
4	Correct	43 ms	6104 KB	Output is correct
5	Correct	145 ms	19780 KB	Output is correct
6	Correct	2 ms	440 KB	Output is correct
7	Correct	5 ms	852 KB	Output is correct
8	Correct	19 ms	2260 KB	Output is correct
9	Correct	44 ms	6096 KB	Output is correct
10	Correct	166 ms	19780 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	5 ms	824 KB	Output is correct
13	Correct	15 ms	2216 KB	Output is correct
14	Correct	45 ms	6112 KB	Output is correct
15	Correct	144 ms	19784 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	8 ms	1216 KB	Output is correct
19	Correct	6 ms	820 KB	Output is correct
20	Correct	17 ms	2304 KB	Output is correct
21	Incorrect	1 ms	300 KB	Output isn't correct
22	Halted	0 ms	0 KB	-