# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
96971 |
2019-02-13T03:09:36 Z |
tieunhi |
Zagrade (COI17_zagrade) |
C++14 |
|
1942 ms |
41080 KB |
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pii pair<int, int>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 300005
#define BASE 37
#define mod 1000000007
#define mid (r + l)/2
using namespace std;
int n, spe[N], sz[N], dd[N], cnt[N], val[N];
long long res = 0;
vector<int> a[N];
void dfsCentroid(int u)
{
spe[u] = 0; sz[u] = 1;
dd[u] = 1;
for (auto v : a[u])
{
if (dd[v]) continue;
dfsCentroid(v);
if (sz[v] > sz[spe[u]]) spe[u] = v;
sz[u] += sz[v];
}
dd[u] = 0;
}
int centroid(int u)
{
int siz = sz[u]/2;
while (sz[spe[u]] > siz)
u = spe[u];
return u;
}
void DFS1(int u, int curVal, int maxVal)
{
dd[u] = 1;
if (curVal >= 0 && curVal == maxVal) res += cnt[maxVal];
for (auto v : a[u])
{
if (dd[v]) continue;
DFS1(v, curVal - val[v], max(maxVal, curVal - val[v]));
}
dd[u] = 0;
}
void DFS2(int u, int curVal, int maxVal)
{
dd[u] = 1;
if (curVal == maxVal) cnt[curVal]++;
for (auto v : a[u])
{
if (dd[v]) continue;
DFS2(v, curVal + val[v], max(maxVal, curVal + val[v]));
}
dd[u] = 0;
}
void solve(int u)
{
dfsCentroid(u);
int siz = sz[u];
u = centroid(u);
dd[u] = 1;
FOR(i, 0, siz) cnt[i] = 0;
if (val[u] == 1) cnt[1]++;
for (auto v : a[u])
{
if (dd[v]) continue;
DFS1(v, -val[v], max(0, -val[v]));
DFS2(v, val[u] + val[v], max({0, val[u], val[u]+val[v]}));
}
for (auto v : a[u])
if (!dd[v]) solve(v);
}
int main()
{
ios_base::sync_with_stdio(0); cout.tie(0);
//freopen("INP.TXT", "r", stdin);
//freopen("OUT.TXT", "w", stdout);
cin >> n;
FOR(i, 1, n)
{
char c; cin >> c;
val[i] = (c == '(') ? 1 : -1;
}
FOR(i, 2, n)
{
int u, v; cin >> u >> v;
a[u].PB(v);
a[v].PB(u);
}
solve(1);
FOR(i, 1, n) dd[i] = 0, val[i] = -val[i];
solve(1);
cout <<res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7524 KB |
Output is correct |
3 |
Correct |
10 ms |
7424 KB |
Output is correct |
4 |
Correct |
11 ms |
7552 KB |
Output is correct |
5 |
Correct |
10 ms |
7424 KB |
Output is correct |
6 |
Correct |
11 ms |
7424 KB |
Output is correct |
7 |
Correct |
9 ms |
7424 KB |
Output is correct |
8 |
Correct |
13 ms |
7552 KB |
Output is correct |
9 |
Correct |
9 ms |
7424 KB |
Output is correct |
10 |
Correct |
12 ms |
7424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
40984 KB |
Output is correct |
2 |
Correct |
570 ms |
41080 KB |
Output is correct |
3 |
Correct |
587 ms |
40936 KB |
Output is correct |
4 |
Correct |
595 ms |
40972 KB |
Output is correct |
5 |
Correct |
534 ms |
40972 KB |
Output is correct |
6 |
Correct |
585 ms |
40992 KB |
Output is correct |
7 |
Correct |
541 ms |
40984 KB |
Output is correct |
8 |
Correct |
535 ms |
40964 KB |
Output is correct |
9 |
Correct |
544 ms |
40932 KB |
Output is correct |
10 |
Correct |
470 ms |
40876 KB |
Output is correct |
11 |
Correct |
515 ms |
40988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7524 KB |
Output is correct |
3 |
Correct |
10 ms |
7424 KB |
Output is correct |
4 |
Correct |
11 ms |
7552 KB |
Output is correct |
5 |
Correct |
10 ms |
7424 KB |
Output is correct |
6 |
Correct |
11 ms |
7424 KB |
Output is correct |
7 |
Correct |
9 ms |
7424 KB |
Output is correct |
8 |
Correct |
13 ms |
7552 KB |
Output is correct |
9 |
Correct |
9 ms |
7424 KB |
Output is correct |
10 |
Correct |
12 ms |
7424 KB |
Output is correct |
11 |
Correct |
504 ms |
40984 KB |
Output is correct |
12 |
Correct |
570 ms |
41080 KB |
Output is correct |
13 |
Correct |
587 ms |
40936 KB |
Output is correct |
14 |
Correct |
595 ms |
40972 KB |
Output is correct |
15 |
Correct |
534 ms |
40972 KB |
Output is correct |
16 |
Correct |
585 ms |
40992 KB |
Output is correct |
17 |
Correct |
541 ms |
40984 KB |
Output is correct |
18 |
Correct |
535 ms |
40964 KB |
Output is correct |
19 |
Correct |
544 ms |
40932 KB |
Output is correct |
20 |
Correct |
470 ms |
40876 KB |
Output is correct |
21 |
Correct |
515 ms |
40988 KB |
Output is correct |
22 |
Correct |
1759 ms |
27100 KB |
Output is correct |
23 |
Correct |
1713 ms |
27068 KB |
Output is correct |
24 |
Correct |
1942 ms |
27092 KB |
Output is correct |
25 |
Correct |
1913 ms |
27084 KB |
Output is correct |
26 |
Correct |
658 ms |
31740 KB |
Output is correct |
27 |
Correct |
780 ms |
29500 KB |
Output is correct |
28 |
Correct |
762 ms |
28720 KB |
Output is correct |
29 |
Correct |
552 ms |
40980 KB |
Output is correct |
30 |
Correct |
511 ms |
40988 KB |
Output is correct |
31 |
Correct |
131 ms |
26728 KB |
Output is correct |
32 |
Correct |
519 ms |
41008 KB |
Output is correct |