Submission #144979

#	Time	Username	Problem	Language	Result	Execution time	Memory
144979		emilem	Zagrade (COI17_zagrade)	C++14	0 / 100	857 ms	20668 KiB

zagrade

#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< pair<int, int> > pref(a.length());
	for (int i = 0; i < pref.size(); ++i)
	{
		pref[i].second = i;
		if (a[i] == '(') ++pref[i].first;
		else --pref[i].first;
		if (i) pref[i].first += pref[i - 1].first;
	}
	vector<int> r(n, -1);
	for (int i = 0; i < n; ++i)
	{
		r[i] = -1;
		int minElem = pref[i].first;
		for (int j = i; j < n; ++j)
		{
			minElem = min(minElem, pref[j].first);
			if (minElem - (i ? pref[i - 1].first : 0) < 0)
				break;
			else
				r[i] = j;
		}
	}
	sort(pref.begin(), pref.end());
	for (int i = 0; i < n; ++i)
		if (r[i] != -1)
			for (int j = i; j < n && pref[j].second <= r[i]; ++j)
				if (pref[j].first == (i ? pref[i - 1].first : 0))
					++ans;
				else
					break;
	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 (false/*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;
	}
 
	char I;
	cin >> I;
}

Compilation message (stderr)

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:40:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if (r[i] != -1)
      ^
zagrade.cpp: In function 'void Dfs(int, int)':
zagrade.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[v].size(); ++i)
                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60