Submission #1083757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083757		8pete8	Raspad (COI17_raspad)	C++17	100 / 100	421 ms	121168 KiB

raspad

#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(){
	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 (stderr)

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 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39