oj.uz

Submission #763834

# Submission time Handle Problem Language Result Execution time Memory
763834 2023-06-22T23:51:47 Z Olympia Zagrade (COI17_zagrade) C++17
10 / 100
 2867 ms 107496 KB 
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <set>
#include <algorithm>
#include <functional>
#include <iomanip>
#define ll long long
using namespace std;
vector<vector<int>> adj;
vector<bool> marked;
vector<int> sz;
map<pair<int,int>,int> myMap;
map<pair<int,int>,int> myMap1;
set<int> mySet;
map<int,int> tot[(int)3e5];
int n;
string s;
int cntr = 0;
int get (char c) {
    return ((c == '(') ? 1 : -1);
}
int find_centroid (int curNode, int prevNode, int net_sz) {
    for (int i: adj[curNode]) {
        if (i != prevNode and !marked[i] and sz[i] * 2 >= net_sz) {
            return find_centroid(i, curNode, net_sz);
        }
    }
    return curNode;
}
void solve (int root) { //this node is our centroid
    std::function<int(int, int)> get_sizes;
    get_sizes = [&get_sizes](int curNode, int prevNode) -> int {
        assert(!marked[curNode]);
        sz[curNode] = 1;
        for (int i: adj[curNode]) {
            if (i != prevNode and !marked[i]) {
                get_sizes(i, curNode);
                sz[curNode] += sz[i];
            }
        }
        return sz[curNode];
    };
    get_sizes(root, root);
    if (sz[root] == 1) {
        return;
    }
    int centroid = find_centroid(root, root, sz[root]);
    marked[centroid] = true;
    int tc = 2;
    while (tc--) {
        for (int x: mySet) {
            tot[x].clear();
        }
        mySet.clear();
        for (int node: adj[centroid]) {
            if (!marked[node]) {
                myMap.clear();
                myMap1.clear();
                std::function<void(int,int,int,int, int, int, int)> dfs;
                dfs = [&dfs](int curNode, int prevNode, int sm, int prefix1, int prefix2, int centroid, int tc) -> void {
                    if (sm <= 0) mySet.insert(0 - sm);
                    myMap[make_pair(sm, prefix1)]++;
                    if (prefix2 >= 0 and sm + get(s[centroid]) >= 0) myMap1[make_pair(sm, prefix1)]++;
                    if (prefix2 >= 0 and sm + get(s[centroid]) >= 0 and tot[sm + get(s[centroid])].count(0 - get(s[centroid]) - sm)) {
                        cntr += tot[sm + get(s[centroid])][0 - get(s[centroid]) - sm] - myMap[make_pair(0 - sm - get(s[centroid]), 0 - get(s[centroid]) - sm)];
                    }
                    if (sm <= 0) tot[0 - sm][prefix1]++;
                    cntr += (sm == 1 and prefix2 == 0 and s[centroid] == ')') * (tc == 0);
                    cntr += (sm + get(s[centroid]) == 0 and prefix1 == -1 and s[centroid] == '(') * (tc == 0);
                    for (int i: adj[curNode]) {
                        if (i != prevNode and !marked[i]) {
                            dfs(i, curNode, sm + get(s[i]), min(min(prefix1, sm + get(s[i])), 0), min(min(prefix2 + get(s[i]), get(s[i])), 0), centroid, tc);
                        }
                    }
                };
                dfs(node, node, get(s[node]), min(0, get(s[node])), min(0, get(s[node])), centroid, tc);
            }
        }
        reverse(adj[centroid].begin(), adj[centroid].end());
    }
    for (int i: adj[centroid]) {
        if (!marked[i]) {
            solve(i);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("zagrade.in.3j.out", "r", stdin);
    //exit(0);
    cin >> n >> s;
    adj.resize(n);
    marked.assign(n, false), sz.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        auto add_edge = [&](int u, int v) {
            adj[u].push_back(v), adj[v].push_back(u);
        };
        add_edge(u, v);
    }
    solve(0);
    cout << cntr << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14444 KB Output is correct
3 Correct 7 ms 14484 KB Output is correct
4 Correct 7 ms 14476 KB Output is correct
5 Correct 10 ms 14544 KB Output is correct
6 Correct 7 ms 14360 KB Output is correct
7 Correct 7 ms 14408 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 8 ms 14480 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 65668 KB Output is correct
2 Correct 1861 ms 79332 KB Output is correct
3 Correct 865 ms 65448 KB Output is correct
4 Correct 1715 ms 76920 KB Output is correct
5 Correct 856 ms 65444 KB Output is correct
6 Correct 934 ms 67864 KB Output is correct
7 Correct 860 ms 65456 KB Output is correct
8 Correct 996 ms 67880 KB Output is correct
9 Correct 851 ms 65376 KB Output is correct
10 Correct 2867 ms 107496 KB Output is correct
11 Incorrect 487 ms 69344 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14444 KB Output is correct
3 Correct 7 ms 14484 KB Output is correct
4 Correct 7 ms 14476 KB Output is correct
5 Correct 10 ms 14544 KB Output is correct
6 Correct 7 ms 14360 KB Output is correct
7 Correct 7 ms 14408 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 8 ms 14480 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 925 ms 65668 KB Output is correct
12 Correct 1861 ms 79332 KB Output is correct
13 Correct 865 ms 65448 KB Output is correct
14 Correct 1715 ms 76920 KB Output is correct
15 Correct 856 ms 65444 KB Output is correct
16 Correct 934 ms 67864 KB Output is correct
17 Correct 860 ms 65456 KB Output is correct
18 Correct 996 ms 67880 KB Output is correct
19 Correct 851 ms 65376 KB Output is correct
20 Correct 2867 ms 107496 KB Output is correct
21 Incorrect 487 ms 69344 KB Output isn't correct
22 Halted 0 ms 0 KB -