Submission #96971

#	Time	Username	Problem	Language	Result	Execution time	Memory
96971		tieunhi	Zagrade (COI17_zagrade)	C++14	100 / 100	1942 ms	41080 KiB

zagrade

#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;
}

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