Submission #829485

#	Time	Username	Problem	Language	Result	Execution time	Memory
829485		ZeroCool	T-Covering (eJOI19_covering)	C++14	100 / 100	382 ms	62852 KiB

covering

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

using ll = long long;
using ld = long double;


void solve(int T);
void pre();

const int mxn = 1e6 + 5;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 1e9 + 7;
const ld eps = 1e-9;

int32_t main(){
	pre();
	int tt = 1;
	//cin>>tt;
	for(int i = 1;i<=tt;i++)solve(i);
    return 0;
}



void pre(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	
}

int A[mxn];

vector<int> g[mxn];

int dir[4][2] = {
	{1,0},
	{-1,0},
	{0,1},
	{0,-1}
};

int n,m;

bool in(int x,int y){
	return x >= 0 && y >= 0 && x<n && y < m;
}

bool cen[mxn];
bool vis[mxn];

int ccnt = 0;
vector<int> cmp;

void dfs(int x){
	vis[x] = true;
	if(!cen[x])cmp.push_back(A[x]);
	else ccnt++;

	for(auto v : g[x]){
		if(vis[v])continue;
		dfs(v);
	}
}

inline int hesh(int a,int b){
	return a * m + b; 
}

void solve(int T){
	cin>>n>>m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin>>A[hesh(i,j)];
		}
	}
	int k;
	cin>>k;
	int ans = 0;

	for(int i = 0;i<k;i++){
		int x,y;
		cin>>x>>y;
		int u = hesh(x,y);

		cen[u] = true;
		ans += A[u];
		for(int j = 0;j<4;j++){
			int nx = x + dir[j][0];
			int ny = y + dir[j][1];

			if(!in(nx,ny))continue;
			int v = hesh(nx,ny);

			g[u].push_back(v);
			g[v].push_back(u);
		}
	}

	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			int u = hesh(i,j);

			if(!vis[u] && cen[u]){
				ccnt = 0;
				cmp.clear();

				dfs(u);

				if(cmp.size() < 3 * ccnt){
					cout<<"No"<<endl;
					return;
				}

				sort(cmp.begin(), cmp.end());
				
				for(int k = 1;k<= 3 * ccnt;k++){
					ans += cmp[cmp.size() - k];
				}
			}
		}
	}

	cout<<ans<<endl;

}

Compilation message (stderr)

covering.cpp: In function 'void solve(long long int)':
covering.cpp:118:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  118 |     if(cmp.size() < 3 * ccnt){
      |        ~~~~~~~~~~~^~~~~~~~~~

• 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