Submission #66309

#	Time	Username	Problem	Language	Result	Execution time	Memory
66309		quoriess	Raspad (COI17_raspad)	C++14	26 / 100	6088 ms	14408 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<vector<int> > dizi;
vector<int> setler,rankler;
int findset(int a){
	if(setler[a]==a)return a;
	setler[a]=findset(setler[a]);
	return setler[a];
}
int setsay=0;
void unyon(int a,int b){
	
	int fa=findset(a),fb=findset(b);
	if(fa==fb)return;
	setsay--;
	//cout << "setsay azaldı: "<<setsay<<"\n";
	if(rankler[fa]>rankler[fb])setler[fb]=fa;
	else if(rankler[fb]>rankler[fa])setler[fa]=fb;
	else{
		rankler[fa]=rankler[fb]+1;
		setler[fb]=fa;
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	//cout <<"aldı\n";
	dizi=vector<vector<int> >(n,vector<int>(m,0));
	setler=rankler=vector<int>(n*m,0);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char c;
			cin>>c;
			dizi[i][j]=c-48;
		}
	}
	//cout <<"aldı\n";
	for (int i = 0; i < n*m; i++)
	{
		setler[i]=i;
	}
	lli tplm=0;
	for (int i = 0; i < n; i++)
	{
		//cout << "tplm: "<<tplm<<"\n";
		setler=rankler=vector<int>(n*m,0);

		for (int i = 0; i < n*m; i++)
		{
			setler[i]=i;
		}
		setsay=0;
		for (int j = i; j < n; j++)
		{
			for (int k = 0; k < m; k++)
			{
				if(!dizi[j][k])continue;
				
				setsay++;
				if(j!=i&&dizi[j-1][k])
					unyon(m*j+k,m*j-m+k);
				if(k!=0&&dizi[j][k-1])
					unyon(m*j+k,m*j+k-1);
				
			}
			//cout << "i: "<<i<<" j: "<<j<<" setsay: "<<setsay<<"\n";
			tplm+=setsay;
			//cout << "setsay:"<<setsay<<"\n";
		}
	}
	cout<<tplm<<"\n";
	return 0;
}

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