| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144935 |
2019-08-18T07:55:11 Z |
SamAnd |
Zagrade (COI17_zagrade) |
C++17 |
|
2009 ms |
91920 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;
vector<int> tt[N + N];
vector<int> t[N + N];
void ubds(int i, int x, int y)
{
i += N;
if (tt[i].empty())
{
t[i].push_back(0);
tt[i].push_back(-N);
vv.push_back(i);
}
t[i].push_back(0);
tt[i].push_back(x);
}
void ubd(int i, int x, int y)
{
i += N;
x = (--upper_bound(tt[i].begin(), tt[i].end(), x)) - tt[i].begin();
while (x < t[i].size())
{
t[i][x] += y;
x += (x & (-x));
}
}
int qry(int i, int x)
{
i += N;
x = (--upper_bound(tt[i].begin(), tt[i].end(), x)) - tt[i].begin();
int ans = 0;
while (x > 0)
{
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)
{
ubds(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 < vv.size(); ++i)
sort(tt[vv[i]].begin(), tt[vv[i]].end());
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)
{
if (i == 1 && j == 1)
cout << "";
ubd(v[j].first, -v[j].second, 1);
}
}
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)
{
t[vv[i]].clear();
tt[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 ubd(int, int, int)':
zagrade.cpp:106:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (x < t[i].size())
~~^~~~~~~~~~~~~
zagrade.cpp: In function 'void solv(int)':
zagrade.cpp:128:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:135:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:146:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vv.size(); ++i)
~~^~~~~~~~~~~
zagrade.cpp:148:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:155:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:162:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:169:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:178:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:187:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j)
~~^~~~~~~~~~
zagrade.cpp:192: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:203:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
scanf(" %s", &bb);
~~~^
zagrade.cpp:223:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a[x].size(); ++i)
~~^~~~~~~~~~~~~
zagrade.cpp:202:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
zagrade.cpp:203:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", &bb);
~~~~~^~~~~~~~~~~~
zagrade.cpp:209: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 |
37 ms |
35576 KB |
Output is correct |
| 2 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 3 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 4 |
Correct |
38 ms |
35568 KB |
Output is correct |
| 5 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 6 |
Correct |
37 ms |
35580 KB |
Output is correct |
| 7 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 8 |
Correct |
38 ms |
35576 KB |
Output is correct |
| 9 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 10 |
Correct |
36 ms |
35576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1407 ms |
71528 KB |
Output is correct |
| 2 |
Correct |
1429 ms |
79240 KB |
Output is correct |
| 3 |
Correct |
1409 ms |
75696 KB |
Output is correct |
| 4 |
Correct |
1453 ms |
78492 KB |
Output is correct |
| 5 |
Correct |
1401 ms |
75676 KB |
Output is correct |
| 6 |
Correct |
1362 ms |
77564 KB |
Output is correct |
| 7 |
Correct |
1410 ms |
75792 KB |
Output is correct |
| 8 |
Correct |
1380 ms |
77572 KB |
Output is correct |
| 9 |
Correct |
1403 ms |
75828 KB |
Output is correct |
| 10 |
Correct |
1229 ms |
91524 KB |
Output is correct |
| 11 |
Correct |
1376 ms |
75632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 2 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 3 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 4 |
Correct |
38 ms |
35568 KB |
Output is correct |
| 5 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 6 |
Correct |
37 ms |
35580 KB |
Output is correct |
| 7 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 8 |
Correct |
38 ms |
35576 KB |
Output is correct |
| 9 |
Correct |
37 ms |
35576 KB |
Output is correct |
| 10 |
Correct |
36 ms |
35576 KB |
Output is correct |
| 11 |
Correct |
1407 ms |
71528 KB |
Output is correct |
| 12 |
Correct |
1429 ms |
79240 KB |
Output is correct |
| 13 |
Correct |
1409 ms |
75696 KB |
Output is correct |
| 14 |
Correct |
1453 ms |
78492 KB |
Output is correct |
| 15 |
Correct |
1401 ms |
75676 KB |
Output is correct |
| 16 |
Correct |
1362 ms |
77564 KB |
Output is correct |
| 17 |
Correct |
1410 ms |
75792 KB |
Output is correct |
| 18 |
Correct |
1380 ms |
77572 KB |
Output is correct |
| 19 |
Correct |
1403 ms |
75828 KB |
Output is correct |
| 20 |
Correct |
1229 ms |
91524 KB |
Output is correct |
| 21 |
Correct |
1376 ms |
75632 KB |
Output is correct |
| 22 |
Correct |
1986 ms |
56152 KB |
Output is correct |
| 23 |
Correct |
1987 ms |
56168 KB |
Output is correct |
| 24 |
Correct |
1966 ms |
55948 KB |
Output is correct |
| 25 |
Correct |
2009 ms |
55912 KB |
Output is correct |
| 26 |
Correct |
1598 ms |
63972 KB |
Output is correct |
| 27 |
Correct |
1557 ms |
61312 KB |
Output is correct |
| 28 |
Correct |
1597 ms |
60780 KB |
Output is correct |
| 29 |
Correct |
1233 ms |
91920 KB |
Output is correct |
| 30 |
Correct |
1250 ms |
91848 KB |
Output is correct |
| 31 |
Correct |
261 ms |
57828 KB |
Output is correct |
| 32 |
Correct |
1384 ms |
76236 KB |
Output is correct |
