oj.uz

Submission #763832

# Submission time Handle Problem Language Result Execution time Memory
763832 2023-06-22T23:49:58 Z Olympia Zagrade (COI17_zagrade) C++17
10 / 100
 3000 ms 113900 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);
                    assert(prefix1 <= 0 and prefix2 <= 0);
                    assert(!marked[curNode]);
                    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) {
                        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("")
    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 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14436 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14360 KB Output is correct
10 Correct 6 ms 14372 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 69848 KB Output is correct
2 Correct 1902 ms 83508 KB Output is correct
3 Correct 903 ms 69768 KB Output is correct
4 Correct 1705 ms 81180 KB Output is correct
5 Correct 891 ms 69728 KB Output is correct
6 Correct 1091 ms 74356 KB Output is correct
7 Correct 900 ms 69720 KB Output is correct
8 Correct 1119 ms 74376 KB Output is correct
9 Correct 895 ms 69620 KB Output is correct
10 Execution timed out 3068 ms 113900 KB Time limit exceeded
11 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 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14436 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14360 KB Output is correct
10 Correct 6 ms 14372 KB Output is correct
11 Correct 919 ms 69848 KB Output is correct
12 Correct 1902 ms 83508 KB Output is correct
13 Correct 903 ms 69768 KB Output is correct
14 Correct 1705 ms 81180 KB Output is correct
15 Correct 891 ms 69728 KB Output is correct
16 Correct 1091 ms 74356 KB Output is correct
17 Correct 900 ms 69720 KB Output is correct
18 Correct 1119 ms 74376 KB Output is correct
19 Correct 895 ms 69620 KB Output is correct
20 Execution timed out 3068 ms 113900 KB Time limit exceeded
21 Halted 0 ms 0 KB -