Submission #144927

# Submission time Handle Problem Language Result Execution time Memory
144927 2019-08-18T07:42:44 Z SamAnd Zagrade (COI17_zagrade) C++17
10 / 100
3000 ms 73028 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;
map<int, int> t[N + N];
void ubd(int i, int x, int y)
{
    i += N;
    x += N;
    vv.push_back(i);
    while (x < N + N)
    {
        t[i][x] += y;
        x += (x & (-x));
    }
}
int qry(int i, int x)
{
    i += N;
    x += N;
    int ans = 0;
    while (x > 0)
    {
        if (t[i].find(x) != t[i].end())
            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)
        {
            ubd(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 < 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)
    {
        if (!t[vv[i]].empty())
            t[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 solv(int)':
zagrade.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
zagrade.cpp:124:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size(); ++j)
                         ~~^~~~~~~~~~
zagrade.cpp:135:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
zagrade.cpp:142:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size(); ++j)
                         ~~^~~~~~~~~~
zagrade.cpp:151:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size(); ++j)
                         ~~^~~~~~~~~~
zagrade.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size(); ++j)
                         ~~^~~~~~~~~~
zagrade.cpp:165: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:176:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
     scanf(" %s", &bb);
                  ~~~^
zagrade.cpp:196:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
zagrade.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
zagrade.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", &bb);
     ~~~~~^~~~~~~~~~~~
zagrade.cpp:182: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 39 ms 35576 KB Output is correct
2 Correct 39 ms 35652 KB Output is correct
3 Correct 39 ms 35576 KB Output is correct
4 Correct 39 ms 35592 KB Output is correct
5 Correct 39 ms 35576 KB Output is correct
6 Correct 39 ms 35660 KB Output is correct
7 Correct 39 ms 35560 KB Output is correct
8 Correct 39 ms 35704 KB Output is correct
9 Correct 35 ms 35576 KB Output is correct
10 Correct 36 ms 35704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 73028 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 39 ms 35576 KB Output is correct
2 Correct 39 ms 35652 KB Output is correct
3 Correct 39 ms 35576 KB Output is correct
4 Correct 39 ms 35592 KB Output is correct
5 Correct 39 ms 35576 KB Output is correct
6 Correct 39 ms 35660 KB Output is correct
7 Correct 39 ms 35560 KB Output is correct
8 Correct 39 ms 35704 KB Output is correct
9 Correct 35 ms 35576 KB Output is correct
10 Correct 36 ms 35704 KB Output is correct
11 Execution timed out 3023 ms 73028 KB Time limit exceeded
12 Halted 0 ms 0 KB -