oj.uz

Submission #609113

# Submission time Handle Problem Language Result Execution time Memory
609113 2022-07-27T12:19:33 Z AliHasanli T-Covering (eJOI19_covering) C++17
25 / 100
 88 ms 37520 KB 
#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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 14 ms 24148 KB Output is correct
3 Correct 20 ms 25164 KB Output is correct
4 Correct 36 ms 27932 KB Output is correct
5 Correct 88 ms 37520 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 16 ms 24216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23960 KB Output is correct
2 Correct 15 ms 24208 KB Output is correct
3 Correct 22 ms 25172 KB Output is correct
4 Correct 34 ms 27916 KB Output is correct
5 Correct 85 ms 37448 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23724 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 14 ms 24212 KB Output is correct
5 Correct 19 ms 25168 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23816 KB Output is correct
2 Incorrect 15 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 14 ms 24148 KB Output is correct
3 Correct 20 ms 25164 KB Output is correct
4 Correct 36 ms 27932 KB Output is correct
5 Correct 88 ms 37520 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Incorrect 16 ms 24216 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 14 ms 24148 KB Output is correct
3 Correct 20 ms 25164 KB Output is correct
4 Correct 36 ms 27932 KB Output is correct
5 Correct 88 ms 37520 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Incorrect 16 ms 24216 KB Output isn't correct
8 Halted 0 ms 0 KB -