oj.uz

Submission #763835

# Submission time Handle Problem Language Result Execution time Memory
763835 2023-06-22T23:54:05 Z Olympia Zagrade (COI17_zagrade) C++17
10 / 100
 1792 ms 102156 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;
vector<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();
                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.push_back(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 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14548 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 14480 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 66636 KB Output is correct
2 Correct 1218 ms 77596 KB Output is correct
3 Correct 787 ms 66108 KB Output is correct
4 Correct 1199 ms 76096 KB Output is correct
5 Correct 824 ms 66260 KB Output is correct
6 Correct 1096 ms 71240 KB Output is correct
7 Correct 783 ms 66156 KB Output is correct
8 Correct 1083 ms 72388 KB Output is correct
9 Correct 771 ms 66136 KB Output is correct
10 Correct 1792 ms 102156 KB Output is correct
11 Incorrect 457 ms 67440 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 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14548 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 14480 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 839 ms 66636 KB Output is correct
12 Correct 1218 ms 77596 KB Output is correct
13 Correct 787 ms 66108 KB Output is correct
14 Correct 1199 ms 76096 KB Output is correct
15 Correct 824 ms 66260 KB Output is correct
16 Correct 1096 ms 71240 KB Output is correct
17 Correct 783 ms 66156 KB Output is correct
18 Correct 1083 ms 72388 KB Output is correct
19 Correct 771 ms 66136 KB Output is correct
20 Correct 1792 ms 102156 KB Output is correct
21 Incorrect 457 ms 67440 KB Output isn't correct
22 Halted 0 ms 0 KB -