Submission #232174

#	Time	Username	Problem	Language	Result	Execution time	Memory
232174		TempoTemp	Zagrade (COI17_zagrade)	C++14	100 / 100	1817 ms	48248 KiB

zagrade

// I don't know ..
#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, M[N], SZ[N], C[N];
char S[N];
long long tot;
vector < int > Adj[N];
pair < int , int > dp[N], pd[N];
void DFSSZ(int v, int p = 0)
{
    SZ[v] = 1;
    for (int u : Adj[v])
        if (u != p && !M[u])
            DFSSZ(u, v), SZ[v] += SZ[u];
}
int Centroid(int v, int p, int _n)
{
    for (int u : Adj[v])
        if (!M[u] && u != p && SZ[u] * 2 > _n)
            return Centroid(u, v, _n);
    return v;
}
void DFSC(int v, int p)
{
    dp[v] = {dp[p].first + S[v], min(dp[p].second + S[v], 0)};
    pd[v] = {pd[p].first - S[v], min(pd[p].second - S[v], 0)};
    for (int u : Adj[v])
        if (u != p && !M[u])
            DFSC(u, v);
}
void DFSADD(int v, int p, int tp)
{
    if (dp[v].second >= 0)
        C[dp[v].first] += tp;
    for (int u : Adj[v])
        if (!M[u] && u != p)
            DFSADD(u, v, tp);
}
void DFSGT(int v, int p)
{
    if (pd[v].second >= 0)
        tot += C[pd[v].first];
    for (int u : Adj[v])
        if (!M[u] && u != p)
            DFSGT(u, v);
}
inline void Solve(int v)
{
    dp[v] = {S[v], min((int)S[v], 0)};
    pd[v] = {0, 0};
    for (int u : Adj[v])
        if (!M[u])
            DFSC(u, v);
    for (int u : Adj[v])
        if (!M[u])
            DFSADD(u, v, 1);
    tot += C[0];
    if (dp[v].second >= 0)
        C[dp[v].first] ++;
    for (int u : Adj[v])
        if (!M[u])
            DFSADD(u, v, -1), DFSGT(u, v), DFSADD(u, v, 1);
    for (int u : Adj[v])
        if (!M[u])
            DFSADD(u, v, -1);
    if (dp[v].second >= 0)
        C[dp[v].first] --;
}
inline void Decompose()
{
    queue < int > qu;
    qu.push(1);
    while (qu.size())
    {
        int v = qu.front();
        DFSSZ(v);
        v = Centroid(v, 0, SZ[v]);
        qu.pop(); M[v] = 1;
        Solve(v);
        for (int u : Adj[v])
            if (!M[u]) qu.push(u);
    }
}
int main()
{
    scanf("%d%s", &n, S + 1);
    for (int i = 1; i <= n; i ++)
        S[i] = (S[i] == '(' ? 1 : -1);
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Adj[v].push_back(u);
        Adj[u].push_back(v);
    }
    Decompose();
    return !printf("%lld\n", tot);
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s", &n, S + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~

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