Submission #350123

#	Time	Username	Problem	Language	Result	Execution time	Memory
350123		arnold518	Raspad (COI17_raspad)	C++14	26 / 100	384 ms	816 KiB

raspad

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;
const int MAXM = 50;

int N, M;
int A[MAXN+10][MAXM+10];

struct UF
{
	int par[MAXN*MAXM+10];
	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	bool Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return 0;
		par[x]=y;
		return 1;
	}
}uf;

int f(int y, int x)
{
	return (y-1)*M+(x-1);
}

ll ans=0;

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%1d", &A[i][j]);

	for(int i=1; i<=N; i++)
	{
		int val=0;
		for(int j=i; j<=N; j++)
		{
			for(int k=1; k<=M; k++)
			{
				uf.par[f(j, k)]=f(j, k);
			}
			for(int k=1; k<=M; k++)
			{
				if(!A[j][k]) continue;
				val++;
				if(j!=i && A[j-1][k]) val-=uf.Union(f(j, k), f(j-1, k));
				if(A[j][k-1]) val-=uf.Union(f(j, k), f(j, k-1));
			}
			//printf("%d %d : %d\n", i, j, val);
			ans+=val;
		}
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:41:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%1d", &A[i][j]);
      |                                                  ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39