oj.uz

Submission #785095

# Submission time Handle Problem Language Result Execution time Memory
785095 2023-07-17T05:03:22 Z 이동현(#10024) Zagrade (COI17_zagrade) C++17
100 / 100
 780 ms 42324 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)3e5 + 4;
int cnt[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int>> way(n);
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }

    int ans = 0;

    vector<int> sz(n), chk(n);
    auto getsz = [&](auto&&self, int x, int pr)->void{
        sz[x] = 1;
        for(auto&nxt:way[x]){
            if(nxt == pr || chk[nxt]) continue;
            self(self, nxt, x);
            sz[x] += sz[nxt];
        }
    };
    auto getcent = [&](auto&&self, int x, int pr, int asz)->int{
        for(auto&nxt:way[x]){
            if(nxt == pr || chk[nxt]) continue;
            if(sz[nxt] * 2 > asz){
                return self(self, nxt, x, asz);
            }
        }
        return x;
    };
    auto sol = [&](auto&&self, int x)->void{
        getsz(getsz, x, -1);
        x = getcent(getcent, x, -1, sz[x]);
        chk[x] = 1;

        // cout << x << endl;

        vector<int> rb;

        int op = 0;
        auto dfs1 = [&](auto&&self, int x, int pr, int now, int mx)->void{
            now += (s[x] == '(' ? 1 : -1);
            mx = max(mx, now);
            if(now >= mx){
                rb.push_back(now);
                ++cnt[now];
                if(!op && !now) ++ans;
                // cout << x << " LEFT " << now << endl;
            }

            for(auto&nxt:way[x]){
                if(nxt == pr || chk[nxt]){
                    continue;
                }
                self(self, nxt, x, now, mx);
            }
        };

        auto dfs2 = [&](auto&&self, int x, int pr, int now, int mx)->void{
            now += (s[x] == ')' ? 1 : -1);
            mx = max(mx, now);
            if(now >= mx){
                ans += cnt[now];
                // cout << x << " RIGHT " << now << endl;
            }

            for(auto&nxt:way[x]){
                if(nxt == pr || chk[nxt]){
                    continue;
                }
                self(self, nxt, x, now, mx);
            }
        };

        for(op = 0; op < 2; ++op){
            if(s[x] == '(' && !op){
                rb.push_back(1);
                ++cnt[1];
            }
            for(auto&nxt:way[x]){
                if(chk[nxt]){
                    continue;
                }

                dfs2(dfs2, nxt, x, 0, 0);
                dfs1(dfs1, nxt, x, (s[x] == '(' ? 1 : -1), (s[x] == '(' ? 1 : 0));
            }

            for(auto&i:rb){
                cnt[i] = 0;
            }
            rb.clear();

            reverse(way[x].begin(), way[x].end());
        }

        for(auto&nxt:way[x]){
            if(chk[nxt]){
                continue;
            }

            self(self, nxt);
        }
    };

    sol(sol, 0);

    cout << ans << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 32780 KB Output is correct
2 Correct 318 ms 32616 KB Output is correct
3 Correct 346 ms 32764 KB Output is correct
4 Correct 305 ms 32708 KB Output is correct
5 Correct 302 ms 32736 KB Output is correct
6 Correct 314 ms 34304 KB Output is correct
7 Correct 300 ms 32788 KB Output is correct
8 Correct 324 ms 34552 KB Output is correct
9 Correct 297 ms 32752 KB Output is correct
10 Correct 284 ms 38132 KB Output is correct
11 Correct 282 ms 35424 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 304 ms 32780 KB Output is correct
12 Correct 318 ms 32616 KB Output is correct
13 Correct 346 ms 32764 KB Output is correct
14 Correct 305 ms 32708 KB Output is correct
15 Correct 302 ms 32736 KB Output is correct
16 Correct 314 ms 34304 KB Output is correct
17 Correct 300 ms 32788 KB Output is correct
18 Correct 324 ms 34552 KB Output is correct
19 Correct 297 ms 32752 KB Output is correct
20 Correct 284 ms 38132 KB Output is correct
21 Correct 282 ms 35424 KB Output is correct
22 Correct 780 ms 29492 KB Output is correct
23 Correct 697 ms 29144 KB Output is correct
24 Correct 662 ms 28888 KB Output is correct
25 Correct 663 ms 28508 KB Output is correct
26 Correct 415 ms 31128 KB Output is correct
27 Correct 416 ms 29776 KB Output is correct
28 Correct 448 ms 29012 KB Output is correct
29 Correct 269 ms 42324 KB Output is correct
30 Correct 273 ms 42268 KB Output is correct
31 Correct 70 ms 31428 KB Output is correct
32 Correct 278 ms 39636 KB Output is correct