Submission #144935

#	Time	Username	Problem	Language	Result	Execution time	Memory
144935		SamAnd	Zagrade (COI17_zagrade)	C++17	100 / 100	2009 ms	91920 KiB

zagrade

#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 (stderr)

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);
         ~~~~~^~~~~~~~~~~~~~~~

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