oj.uz

답안 #66309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66309 2018-08-10T07:56:25 Z quoriess Raspad (COI17_raspad) C++14
26 / 100
 6000 ms 14408 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 11 ms 472 KB Output is correct
3 Correct 7 ms 784 KB Output is correct
4 Correct 6 ms 784 KB Output is correct
5 Correct 7 ms 784 KB Output is correct
6 Correct 7 ms 784 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 11 ms 472 KB Output is correct
3 Correct 7 ms 784 KB Output is correct
4 Correct 6 ms 784 KB Output is correct
5 Correct 7 ms 784 KB Output is correct
6 Correct 7 ms 784 KB Output is correct
7 Correct 296 ms 1624 KB Output is correct
8 Correct 4 ms 1624 KB Output is correct
9 Correct 730 ms 1760 KB Output is correct
10 Correct 219 ms 1760 KB Output is correct
11 Correct 483 ms 1956 KB Output is correct
12 Correct 147 ms 1956 KB Output is correct
13 Correct 396 ms 1956 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6088 ms 14408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 11 ms 472 KB Output is correct
3 Correct 7 ms 784 KB Output is correct
4 Correct 6 ms 784 KB Output is correct
5 Correct 7 ms 784 KB Output is correct
6 Correct 7 ms 784 KB Output is correct
7 Correct 296 ms 1624 KB Output is correct
8 Correct 4 ms 1624 KB Output is correct
9 Correct 730 ms 1760 KB Output is correct
10 Correct 219 ms 1760 KB Output is correct
11 Correct 483 ms 1956 KB Output is correct
12 Correct 147 ms 1956 KB Output is correct
13 Correct 396 ms 1956 KB Output is correct
14 Execution timed out 6088 ms 14408 KB Time limit exceeded
15 Halted 0 ms 0 KB -