oj.uz

Submission #1083757

# Submission time Handle Problem Language Result Execution time Memory
1083757 2024-09-04T04:21:56 Z 8pete8 Raspad (COI17_raspad) C++17
100 / 100
 421 ms 121168 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(){
	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 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 22620 KB Output is correct
2 Correct 158 ms 95312 KB Output is correct
3 Correct 128 ms 87888 KB Output is correct
4 Correct 114 ms 118608 KB Output is correct
5 Correct 42 ms 26704 KB Output is correct
6 Correct 132 ms 88052 KB Output is correct
7 Correct 92 ms 87928 KB Output is correct
8 Correct 84 ms 70560 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 4 ms 1188 KB Output is correct
10 Correct 2 ms 1368 KB Output is correct
11 Correct 4 ms 1628 KB Output is correct
12 Correct 2 ms 1140 KB Output is correct
13 Correct 3 ms 1116 KB Output is correct
14 Correct 29 ms 22620 KB Output is correct
15 Correct 158 ms 95312 KB Output is correct
16 Correct 128 ms 87888 KB Output is correct
17 Correct 114 ms 118608 KB Output is correct
18 Correct 42 ms 26704 KB Output is correct
19 Correct 132 ms 88052 KB Output is correct
20 Correct 92 ms 87928 KB Output is correct
21 Correct 84 ms 70560 KB Output is correct
22 Correct 280 ms 86608 KB Output is correct
23 Correct 313 ms 91472 KB Output is correct
24 Correct 251 ms 91472 KB Output is correct
25 Correct 380 ms 121168 KB Output is correct
26 Correct 312 ms 97620 KB Output is correct
27 Correct 298 ms 91220 KB Output is correct
28 Correct 275 ms 90412 KB Output is correct
29 Correct 421 ms 113748 KB Output is correct
30 Correct 310 ms 97616 KB Output is correct
31 Correct 309 ms 104016 KB Output is correct
32 Correct 216 ms 91476 KB Output is correct
33 Correct 214 ms 82256 KB Output is correct
34 Correct 267 ms 82512 KB Output is correct