oj.uz

Submission #144957

# Submission time Handle Problem Language Result Execution time Memory
144957 2019-08-18T09:31:16 Z arayi Zagrade (COI17_zagrade) C++17
40 / 100
 202 ms 19980 KB 
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#define fr first
#define sc second
#define MP make_pair
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
using namespace std;

lli gcd(lli a, lli b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
lli cg(lli n) {
	return n ^ (n >> 1);
}
lli SUM(lli a)
{
	return (a * (a + 1) / 2);
}
bool CAN(int x, int y, int n, int m)
{
	if (x >= 0 && y >= 0 && x < n && y < m)
	{
		return true;
	}
	return false;
}
double her(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
string strsum(string a, string b)
{
	int p = 0;
	string c;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	if (b.length() < a.length())
	{
		for (int i = b.length(); i < a.length(); i++)
		{
			b += "0";
		}
	}
	else
	{
		for (int i = a.length(); i < b.length(); i++)
		{
			a += "0";
		}
	}

	a += "0", b += "0";
	for (int i = 0; i < a.length(); i++)
	{
		c += (a[i] - '0' + b[i] - '0' + p) % 10 + '0';
		p = (a[i] + b[i] - '0' - '0' + p) / 10;
	}
	if (c[c.length() - 1] == '0') c.erase(c.length() - 1, 1);
	reverse(c.begin(), c.end());
	return c;
}
string strmin(string a, string b)
{
	if (a.length() > b.length()) return b;
	if (b.length() > a.length()) return a;
	for (int i = 0; i < a.length(); i++)
	{
		if (a[i] > b[i]) return b;
		if (b[i] > a[i]) return a;
	}
	return a;
}

char vow[] = { 'a', 'e', 'i', 'o', 'u' };
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };



const int N = 3e5 + 30;
const lli mod = 1000000007;
int n, sm;

vector <int> g[N];
string s;
lli pat, pr[N];
int nax[2 * N], sum[2 * N];
stack <int> col;
void dfs(int v, int val, int p)
{
	if (val < 0) return;
	if (val == 0) pat++;
	for (auto q : g[v])
	{
		if (p != q)
		{
			if (s[q - 1] == '(') dfs(q, val + 1, v);
			else dfs(q, val - 1, v);
		}
	}
}
int main()
{
	fastio;
	cin >> n >> s;
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		g[a].PB(b);
		g[b].PB(a);
	}
	if (n <= 1000)
	{
		for (int i = 1; i <= n; i++)
		{
			if (s[i - 1] == '(')
				dfs(i, 1, 0);
		}
	}
	else
	{
		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == '(') col.push(1);
			else
			{
				if (col.empty()) pr[0] = 0;
				else
				{
					pr[col.size()] = 0;
					col.pop();
					pat++;
					pat += pr[col.size()];
					pr[col.size()]++;
				}
			}
		}
		memset(pr, 0, sizeof(pr));
		while (!col.empty()) col.pop();
		reverse(s.begin(), s.end());
		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == '(') col.push(1);
			else
			{
				if (col.empty()) pr[0] = 0;
				else
				{
					pr[col.size()] = 0;
					col.pop();
					pat++;
					pat += pr[col.size()];
					pr[col.size()]++;
				}
			}
		}
	}
	cout << pat;
	return 0;
}

Compilation message

zagrade.cpp: In function 'std::__cxx11::string strsum(std::__cxx11::string, std::__cxx11::string)':
zagrade.cpp:57:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = b.length(); i < a.length(); i++)
                            ~~^~~~~~~~~~~~
zagrade.cpp:64:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = a.length(); i < b.length(); i++)
                            ~~^~~~~~~~~~~~
zagrade.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.length(); i++)
                  ~~^~~~~~~~~~~~
zagrade.cpp: In function 'std::__cxx11::string strmin(std::__cxx11::string, std::__cxx11::string)':
zagrade.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.length(); i++)
                  ~~^~~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:141:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.length(); i++)
                   ~~^~~~~~~~~~~~
zagrade.cpp:160:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.length(); i++)
                   ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 19468 KB Output is correct
2 Correct 128 ms 19440 KB Output is correct
3 Correct 122 ms 19464 KB Output is correct
4 Correct 121 ms 19468 KB Output is correct
5 Correct 125 ms 19480 KB Output is correct
6 Correct 122 ms 19596 KB Output is correct
7 Correct 124 ms 19472 KB Output is correct
8 Correct 127 ms 19596 KB Output is correct
9 Correct 123 ms 19468 KB Output is correct
10 Correct 118 ms 19980 KB Output is correct
11 Correct 120 ms 19388 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7416 KB Output is correct
2 Correct 16 ms 7416 KB Output is correct
3 Correct 15 ms 7416 KB Output is correct
4 Correct 12 ms 7416 KB Output is correct
5 Correct 13 ms 7416 KB Output is correct
6 Correct 16 ms 7416 KB Output is correct
7 Correct 16 ms 7416 KB Output is correct
8 Correct 10 ms 7416 KB Output is correct
9 Correct 13 ms 7416 KB Output is correct
10 Correct 13 ms 7416 KB Output is correct
11 Correct 123 ms 19468 KB Output is correct
12 Correct 128 ms 19440 KB Output is correct
13 Correct 122 ms 19464 KB Output is correct
14 Correct 121 ms 19468 KB Output is correct
15 Correct 125 ms 19480 KB Output is correct
16 Correct 122 ms 19596 KB Output is correct
17 Correct 124 ms 19472 KB Output is correct
18 Correct 127 ms 19596 KB Output is correct
19 Correct 123 ms 19468 KB Output is correct
20 Correct 118 ms 19980 KB Output is correct
21 Correct 120 ms 19388 KB Output is correct
22 Incorrect 202 ms 19888 KB Output isn't correct
23 Halted 0 ms 0 KB -