| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144927 |
2019-08-18T07:42:44 Z |
SamAnd |
Zagrade (COI17_zagrade) |
C++17 |
|
3000 ms |
73028 KB |
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 300005;
long long ans;
int n;
char bb[N], b[N];
vector<int> a[N];
bool c[N];
int q[N];
void dfs0(int x, int p)
{
q[x] = 1;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (c[h])
continue;
dfs0(h, x);
q[x] += q[h];
}
}
int dfsf(int x, int p, int xx)
{
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (c[h])
continue;
if (q[h] > q[xx] / 2)
return dfsf(h, x, xx);
}
return x;
}
pair<int, int> mer(const pair<int, int>& a, const pair<int, int>& b)
{
return m_p(a.first + b.first, min(a.second, a.first + b.second));
}
vector<pair<int, int> > v;
void dfs1(int x, int p, pair<int, int> pp)
{
pair<int, int> u;
if (b[x] == ')')
u = mer(pp, m_p(-1, -1));
else
u = mer(pp, m_p(1, 0));
v.push_back(u);
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (c[h])
continue;
dfs1(h, x, u);
}
}
void dfs2(int x, int p, pair<int, int> pp)
{
pair<int, int> u;
if (b[x] == ')')
u = mer(m_p(-1, -1), pp);
else
u = mer(m_p(1, 0), pp);
v.push_back(u);
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (c[h])
continue;
dfs2(h, x, u);
}
}
vector<int> vv;
map<int, int> t[N + N];
void ubd(int i, int x, int y)
{
i += N;
x += N;
vv.push_back(i);
while (x < N + N)
{
t[i][x] += y;
x += (x & (-x));
}
}
int qry(int i, int x)
{
i += N;
x += N;
int ans = 0;
while (x > 0)
{
if (t[i].find(x) != t[i].end())
ans += t[i][x];
x -= (x & (-x));
}
return ans;
}
void solv(int x)
{
vv.clear();
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (c[h])
continue;
v.clear();
dfs1(h, h, m_p(0, 0));
for (int j = 0; j < v.size(); ++j)
{
ubd(v[j].first, -v[j].second, 1);
if (b[x] == '(')
{
pair<int, int> u = mer(m_p(1, 0), v[j]);
if (u.first == 0 && u.second >= 0)
++ans;
}
}
}
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (c[h])
continue;
v.clear();
dfs1(h, h, m_p(0, 0));
for (int j = 0; j < v.size(); ++j)
{
ubd(v[j].first, -v[j].second, -1);
}
v.clear();
if (b[x] == ')')
dfs2(h, h, m_p(-1, -1));
else
dfs2(h, h, m_p(1, 0));
for (int j = 0; j < v.size(); ++j)
{
if (v[j].first == 0 && v[j].second >= 0)
++ans;
if (v[j].second >= 0)
ans += qry(-v[j].first, v[j].first);
}
v.clear();
dfs1(h, h, m_p(0, 0));
for (int j = 0; j < v.size(); ++j)
{
ubd(v[j].first, -v[j].second, 1);
}
}
for (int i = 0; i < vv.size(); ++i)
{
if (!t[vv[i]].empty())
t[vv[i]].clear();
}
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &n);
scanf(" %s", &bb);
for (int i = 1; i <= n; ++i)
b[i] = bb[i - 1];
for (int i = 0; i < n - 1; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
queue<int> q;
q.push(1);
while (!q.empty())
{
int x = q.front();
q.pop();
dfs0(x, x);
x = dfsf(x, x, x);
c[x] = true;
solv(x);
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (!c[h])
q.push(h);
}
}
cout << ans << endl;
return 0;
}
Compilation message
zagrade.cpp: In function 'void dfs0(int, int)':
zagrade.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp: In function 'int dfsf(int, int, int)':
zagrade.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp: In function 'void dfs1(int, int, std::pair<int, int>)':
zagrade.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp: In function 'void dfs2(int, int, std::pair<int, int>)':
zagrade.cpp:76:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp: In function 'void solv(int)':
zagrade.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:124:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:135:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:142:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:151:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:165:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vv.size(); ++i)
~~^~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:176:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
scanf(" %s", &bb);
~~~^
zagrade.cpp:196:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
zagrade.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", &bb);
~~~~~^~~~~~~~~~~~
zagrade.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
35576 KB |
Output is correct |
| 2 |
Correct |
39 ms |
35652 KB |
Output is correct |
| 3 |
Correct |
39 ms |
35576 KB |
Output is correct |
| 4 |
Correct |
39 ms |
35592 KB |
Output is correct |
| 5 |
Correct |
39 ms |
35576 KB |
Output is correct |
| 6 |
Correct |
39 ms |
35660 KB |
Output is correct |
| 7 |
Correct |
39 ms |
35560 KB |
Output is correct |
| 8 |
Correct |
39 ms |
35704 KB |
Output is correct |
| 9 |
Correct |
35 ms |
35576 KB |
Output is correct |
| 10 |
Correct |
36 ms |
35704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3023 ms |
73028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
35576 KB |
Output is correct |
| 2 |
Correct |
39 ms |
35652 KB |
Output is correct |
| 3 |
Correct |
39 ms |
35576 KB |
Output is correct |
| 4 |
Correct |
39 ms |
35592 KB |
Output is correct |
| 5 |
Correct |
39 ms |
35576 KB |
Output is correct |
| 6 |
Correct |
39 ms |
35660 KB |
Output is correct |
| 7 |
Correct |
39 ms |
35560 KB |
Output is correct |
| 8 |
Correct |
39 ms |
35704 KB |
Output is correct |
| 9 |
Correct |
35 ms |
35576 KB |
Output is correct |
| 10 |
Correct |
36 ms |
35704 KB |
Output is correct |
| 11 |
Execution timed out |
3023 ms |
73028 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
