제출 #609113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
609113		AliHasanli	T-Covering (eJOI19_covering)	C++17	25 / 100	88 ms	37520 KiB

covering

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define black_tree tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define gp __gnu_pbds
#define INF 1000000000
#define MOD 1000000007
#define MAX 1000001
#define endl '\n'
#define ll long long
#define ld long double
#define lli long long int
#define ull unsigned long long
#define ulli unsigned long long int
#define pb push_back
#define pf push_front
#define ook order_of_key
#define fbo find_by_order
#define np next_permutation
#define mp make_pair
#define eb emplace_back 
#define me max_element
#define lb lower_bound 
#define ub upper_bound
#define bs binary_search
#define ff first
#define ss second
using namespace std;
using namespace gp;
vector<ll>val,g[MAX];
ll n,m,k,a,b,c,d,e,t=1,x,y,say,ans,node=1,v[MAX];
bool dp[MAX],used[MAX];
void dfs(ll s){
	used[s]=true;
	if(dp[s]){
		say++;
	}
	else{
		val.pb(v[s]);
	}
	for(int i=0;i<g[s].size();i++){
		if(!used[g[s][i]]){
			dfs(g[s][i]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a;
			v[t++]=a;
		}
	}
	cin>>k;
	for(int i=0;i<k;i++){
		cin>>x>>y;
		++x,++y;
		a=(x-1)*n+y,b=(x-2)*n+y,c=(x-1)*n+y-1,d=x*n+y,e=(x-1)*n+y+1,ans+=v[a];
		dp[a]=true;
		if(x>1){
			g[a].pb(b);
			g[b].pb(a);
		}
		if(y>1){
			g[a].pb(c);
			g[c].pb(a);
		}
		if(x<m){
			g[a].pb(d);
			g[d].pb(a);
		}
		if(y<n){
		   g[a].pb(e);
		   g[e].pb(a);
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(!used[node]){
				val.clear();
				say=0;
				dfs(node);
				sort(val.rbegin(),val.rend());
				if(3*say>val.size()){
					cout<<"NO";
					return 0;
				}
				for(int k=0;k<3*say;k++){
					ans+=val[k];
				}
			}
			node++;
		}
	}
	cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'void dfs(long long int)':
covering.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<g[s].size();i++){
      |              ~^~~~~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:88:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     if(3*say>val.size()){
      |        ~~~~~^~~~~~~~~~~

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