oj.uz

Submission #144937

# Submission time Handle Problem Language Result Execution time Memory
144937 2019-08-18T07:57:17 Z emilem Raspad (COI17_raspad) C++14
9 / 100
 6000 ms 4740 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 SuffAns(int l, int r)
{
	int res = 0;
	Dsu dsu;
	for (int i = r; i >= l; --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 >= i && i1 <= r && 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 Solve(int vl, int vr)
{
	if (vl == vr)
		return PrefAns(vl, vr);
	int vm = vl + (vr - vl) / 2;
	int ans = Solve(vl, vm) + Solve(vm + 1, vr);
}
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 += SuffAns(0, i);
	cout << ans << endl;

	char I;
	cin >> I;
}

Compilation message

raspad.cpp: In function 'int Solve(int, int)':
raspad.cpp:110:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = Solve(vl, vm) + Solve(vm + 1, vr);
      ^~~
raspad.cpp:111:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 209 ms 924 KB Output is correct
3 Correct 84 ms 632 KB Output is correct
4 Correct 94 ms 636 KB Output is correct
5 Correct 91 ms 636 KB Output is correct
6 Correct 147 ms 760 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 209 ms 924 KB Output is correct
3 Correct 84 ms 632 KB Output is correct
4 Correct 94 ms 636 KB Output is correct
5 Correct 91 ms 636 KB Output is correct
6 Correct 147 ms 760 KB Output is correct
7 Correct 4815 ms 1992 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Execution timed out 6074 ms 2420 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 6076 ms 4740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 209 ms 924 KB Output is correct
3 Correct 84 ms 632 KB Output is correct
4 Correct 94 ms 636 KB Output is correct
5 Correct 91 ms 636 KB Output is correct
6 Correct 147 ms 760 KB Output is correct
7 Correct 4815 ms 1992 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Execution timed out 6074 ms 2420 KB Time limit exceeded
10 Halted 0 ms 0 KB -