oj.uz

Submission #144899

# Submission time Handle Problem Language Result Execution time Memory
144899 2019-08-18T06:46:38 Z emilem Zagrade (COI17_zagrade) C++14
10 / 100
 395 ms 18208 KB 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long ans;
int n;
int op, clos;
string path;
vector< vector<int> > nei;
string a;

long long Chain(const string& a)
{
	vector<int> pref(a.length());
	for (int i = 0; i < pref.size(); ++i)
	{
		if (a[i] == '(') ++pref[i];
		else --pref[i];
		if (i) pref[i] += pref[i - 1];
	}
	return 0;
}
void Dfs(int v, int par)
{
	if (op == clos && a[v] == ')')
		return;
	if (a[v] == ')') ++clos;
	else ++op;
	path += a[v];
	if (clos == op)
		++ans;
	for (int i = 0; i < nei[v].size(); ++i)
	{
		int to = nei[v][i];
		if (to == par) continue;
		Dfs(to, v);
	}
	path.pop_back();
	if (a[v] == ')') --clos;
	else --op;
}
int main()
{
	cin >> n;
	nei.resize(n);
	cin >> a;
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		cin >> u >> v; --u; --v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	if (n <= 1000)
	{
		for (int v = 0; v < n; ++v)
		{
			op = clos = 0;
			path = "";
			Dfs(v, -1);
		}
		cout << ans << endl;
		return 0;
	}
	else // Is a chain.
	{
		ans += Chain(a);
		reverse(a.begin(), a.end());
		ans += Chain(a);
		cout << ans << endl;

		char I;
		cin >> I;
		return 0;
		vector<int> st(n, -1), dp(n);
		for (int i = 0; i < n; ++i)
		{
			if (op == clos && a[i] == ')')
			{
				op = clos = 0;
				path = "";
				continue;
			}
			if (a[1] == ')') ++clos;
			else ++op;
			path += a[i];
			if (op == clos)
			{
				st[i] = i - (int)path.length() + 1;
				op = clos = 0;
				path = "";
			}
		}
		long long cnt = 0;
		for (int i = n - 1; i >= 0; )
		{
			if (st[i] == -1)
			{

				ans += (cnt * (cnt - 1)) / 2;
				cnt = 0;
				--i;
			}
			else
			{
				++cnt;
				i = st[i] - 1;
				if (i < 0)
					ans += (cnt * (cnt - 1)) / 2;
			}
		}
		cout << ans << endl;
	}

	char I;
	cin >> I;
}

Compilation message

zagrade.cpp: In function 'long long int Chain(const string&)':
zagrade.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pref.size(); ++i)
                  ~~^~~~~~~~~~~~~
zagrade.cpp: In function 'void Dfs(int, int)':
zagrade.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[v].size(); ++i)
                  ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 376 KB Output is correct
2 Correct 18 ms 376 KB Output is correct
3 Correct 15 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 11 ms 376 KB Output is correct
6 Correct 18 ms 376 KB Output is correct
7 Correct 16 ms 376 KB Output is correct
8 Correct 7 ms 380 KB Output is correct
9 Correct 12 ms 376 KB Output is correct
10 Correct 11 ms 376 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 395 ms 18208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 376 KB Output is correct
2 Correct 18 ms 376 KB Output is correct
3 Correct 15 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 11 ms 376 KB Output is correct
6 Correct 18 ms 376 KB Output is correct
7 Correct 16 ms 376 KB Output is correct
8 Correct 7 ms 380 KB Output is correct
9 Correct 12 ms 376 KB Output is correct
10 Correct 11 ms 376 KB Output is correct
11 Incorrect 395 ms 18208 KB Output isn't correct
12 Halted 0 ms 0 KB -