oj.uz

Submission #144928

# Submission time Handle Problem Language Result Execution time Memory
144928 2019-08-18T07:44:47 Z emilem Raspad (COI17_raspad) C++14
9 / 100
 6000 ms 91568 KB 
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, m;
vector< vector<char> > a;

class Dsu
{
public:
	Dsu()
		: count(0)
	{}
	void MakeSet(int x, int y)
	{
		// cerr << "Make (" << x << ", " << y << ")\n";
		++count;
		par[make_pair(x, y)] = make_pair(x, y);
	}
	pair<int, int> GetSet(int x, int y)
	{
		pair<int, int> p = make_pair(x, y);
		if (par[p] == p)
			return p;
		return par[p] = GetSet(par[p].first, par[p].second);
	}
	void Union(int x1, int y1, int x2, int y2)
	{
		pair<int, int> p1 = GetSet(x1, y1);
		pair<int, int> p2 = GetSet(x2, y2);
		if (p1 == p2)
			return;
		// cerr << "Union (" << x1 << ", " << y1 << ") and (" << x2 << ", " << y2 << ")\n";
		if (sz[p1] > sz[p2])
			swap(p1, p2);
		sz[p2] += sz[p1];
		par[p1] = p2;
		--count;
	}
	int Size() { return count; }

private:
	int count;
	map<pair<int, int>, pair<int, int>> par;
	map<pair<int, int>, int> sz;
};
int PrefAns(int l, int r)
{
	int res = 0;
	Dsu dsu;
	for (int i = l; i <= r; ++i)
	{
		for (int j = 0; j < m; ++j)
			if (a[i][j] == '1')
			{
				dsu.MakeSet(i, j);
				const int di[] = {-1, 0};
				const int dj[] = {0, -1};
				for (int d = 0; d < 2; ++d)
				{
					int i1 = i + di[d], j1 = j + dj[d];
					if (i1 >= l && i1 <= i && j1 >= 0 && j1 < m && a[i1][j1] == '1')
						dsu.Union(i, j, i1, j1);
				}
			}
		// cerr << "**************dsu size: " << dsu.Size() << endl;
		res += dsu.Size();
	}
	/*
	char I;
	cin >> I;
	*/
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	a.resize(n, vector<char>(m));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> a[i][j];
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans += PrefAns(i, n - 1);
	cout << ans << endl;

	char I;
	cin >> I;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 194 ms 988 KB Output is correct
3 Correct 89 ms 632 KB Output is correct
4 Correct 105 ms 760 KB Output is correct
5 Correct 85 ms 632 KB Output is correct
6 Correct 131 ms 632 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 194 ms 988 KB Output is correct
3 Correct 89 ms 632 KB Output is correct
4 Correct 105 ms 760 KB Output is correct
5 Correct 85 ms 632 KB Output is correct
6 Correct 131 ms 632 KB Output is correct
7 Correct 4522 ms 2168 KB Output is correct
8 Correct 20 ms 376 KB Output is correct
9 Execution timed out 6055 ms 4216 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6039 ms 91568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 194 ms 988 KB Output is correct
3 Correct 89 ms 632 KB Output is correct
4 Correct 105 ms 760 KB Output is correct
5 Correct 85 ms 632 KB Output is correct
6 Correct 131 ms 632 KB Output is correct
7 Correct 4522 ms 2168 KB Output is correct
8 Correct 20 ms 376 KB Output is correct
9 Execution timed out 6055 ms 4216 KB Time limit exceeded
10 Halted 0 ms 0 KB -