| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66309 |
2018-08-10T07:56:25 Z |
quoriess |
Raspad (COI17_raspad) |
C++14 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6088 ms |
14408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
