oj.uz

Submission #1083758

# Submission time Handle Problem Language Result Execution time Memory
1083758 2024-09-04T04:22:12 Z 8pete8 Raspad (COI17_raspad) C++17
100 / 100
 346 ms 117292 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e5+5,inf=1e18,minf=-1e18,lg=30,valbound=1e9;
//#undef int
int k,m,q,p,h,w,n;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);	
	freopen((name+".in").c_str(),"r",stdin);	
	freopen((name+".out").c_str(),"w",stdout);
}
int grid[mxn+10][55],vis[mxn+10][55];
int ans=0,x=inf,y=minf;
int u[8]={1,-1,0,0,1,1,-1,-1},r[8]={0,0,1,-1,1,-1,1,-1};
void get(int cx,int cy){
	x=min(x,cx);
	y=max(y,cx);
	vis[cx][cy]=1;
	for(int i=0;i<8;i++){
		int nx=cx+u[i],ny=cy+r[i];
		if(nx<=0||nx>n||ny<=0||ny>m){
			x=1,y=n;//border case ->dont count
			continue;
		}
		if(vis[nx][ny])continue;
		if(grid[nx][ny])continue;
		get(nx,ny);
	}
}
int32_t main(){
	fastio
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string a;cin>>a;
		for(int j=0;j<m;j++)grid[i][j+1]=a[j]-'0';
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(grid[i][j])ans+=(i*(n-i+1));
	for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(grid[i][j]&&grid[i-1][j])ans-=((i-1)*(n-i+1));
	for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)if(grid[i][j]&&grid[i][j-1])ans-=(i*(n-i+1));
	
	for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)if(grid[i][j]&&grid[i][j-1]&&grid[i-1][j]&&grid[i-1][j-1])ans+=((i-1)*(n-i+1));
	//case 4
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!vis[i][j]&&grid[i][j]==0){
		x=n,y=1;
		get(i,j);
		ans+=((x-1)*(n-y));
	}
	cout<<ans;
}
/*
what if we look at each cell as a seperated node
then we can see that the vertical edges connect 2 node together
so we will know that l,r that cover i will have comp -=1

how about the horizontal edges?

we can make all the node that shared vertical edge into one comp

we can make a graph with only horizontal edges

we can see that for a cycle let x,y = min and max row in the cycle
we can see that one of the edge is useless as it connect 2 of the same comp
when there are multiple cycle in a cycle we will take min,max from the small cycle
each cycle will make a hole? except for the size 4
we can oversubtract then add back by counting holes?

4 4
1101
1111
1010
1011

5 7
0100010
0111110
0101001
1111011
0100100

4 12
011111010111
110000101001
110111101111
111101111111
*/

Compilation message

raspad.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
raspad.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
raspad.cpp:46:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | void get(int cx,int cy){
      |                       ^
raspad.cpp:61:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 | int32_t main(){
      |              ^
raspad.cpp: In function 'void setIO(std::string)':
raspad.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raspad.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 1 ms 1168 KB Output is correct
11 Correct 4 ms 1628 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21852 KB Output is correct
2 Correct 144 ms 93784 KB Output is correct
3 Correct 105 ms 86312 KB Output is correct
4 Correct 102 ms 117292 KB Output is correct
5 Correct 35 ms 26192 KB Output is correct
6 Correct 115 ms 86608 KB Output is correct
7 Correct 68 ms 86356 KB Output is correct
8 Correct 65 ms 69200 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 1 ms 1168 KB Output is correct
11 Correct 4 ms 1628 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 16 ms 21852 KB Output is correct
15 Correct 144 ms 93784 KB Output is correct
16 Correct 105 ms 86312 KB Output is correct
17 Correct 102 ms 117292 KB Output is correct
18 Correct 35 ms 26192 KB Output is correct
19 Correct 115 ms 86608 KB Output is correct
20 Correct 68 ms 86356 KB Output is correct
21 Correct 65 ms 69200 KB Output is correct
22 Correct 222 ms 83532 KB Output is correct
23 Correct 247 ms 86356 KB Output is correct
24 Correct 182 ms 86492 KB Output is correct
25 Correct 291 ms 116304 KB Output is correct
26 Correct 301 ms 92756 KB Output is correct
27 Correct 233 ms 87120 KB Output is correct
28 Correct 222 ms 86340 KB Output is correct
29 Correct 346 ms 108784 KB Output is correct
30 Correct 235 ms 92660 KB Output is correct
31 Correct 248 ms 98900 KB Output is correct
32 Correct 144 ms 86612 KB Output is correct
33 Correct 153 ms 77904 KB Output is correct
34 Correct 202 ms 78164 KB Output is correct