oj.uz

Submission #785129

# Submission time Handle Problem Language Result Execution time Memory
785129 2023-07-17T05:48:12 Z 이성호(#10023) Zagrade (COI17_zagrade) C++17
30 / 100
 191 ms 121120 KB 
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> adj[300005], g[300005];
int N, deep[300005], a[300005], prf[300005], par[300005];
map<int, int> cnt[300005], cnt2[300005];
int id[300005];
void dfs(int v, int p)
{
    deep[v] = 1;
    par[v] = p;
    prf[v] = prf[p] + a[v];
    for (int i:adj[v]) {
        if (i != p) g[v].push_back(i);
    }
    for (int i = 0; i < (int)g[v].size(); i++) {
        dfs(g[v][i], v);
        if (deep[v] < deep[g[v][i]] + 1) {
            deep[v] = deep[g[v][i]] + 1;
            swap(g[v][i], g[v][0]);
        }
    }
}
long long ans = 0;
void dfs2(int v, int p)
{
    if (g[v].empty()) {
        id[v] = v;
        if (a[v] == 1) cnt[id[v]][prf[v]]++;
        else cnt2[id[v]][prf[v]]++;
        return;
    }
    for (int i:g[v]) dfs2(i, v);
    id[v] = id[g[v][0]];
    //id[v]�� v�� �����ؾ� ��
    //prf[v] �̸��� cnt ����, prf[v] �ʰ��� cnt2 ����
    auto it = cnt[id[v]].begin();
    while (it != cnt[id[v]].end()) {
        if (it -> first < prf[v]) {
            it = cnt[id[v]].erase(it);
        }
        else break;
    }
    auto it2 = cnt2[id[v]].rbegin();
    while (it2 != cnt2[id[v]].rend()) {
        if (it2 -> first > prf[v]) {
            it2 = decltype(it2)(cnt2[id[v]].erase(next(it2).base()));
        }
        else break;
    }
    if (a[v] == 1) ans += cnt2[id[v]][prf[par[v]]];
    else ans += cnt[id[v]][prf[par[v]]];
    cnt[id[v]][prf[v]]++; cnt2[id[v]][prf[v]]++;
    for (int i:g[v]) {
        if (i != g[v][0]) {
            for (pair<int, int> p:cnt[id[i]]) {
                ans += (long long) p.second * cnt2[id[v]][prf[par[v]] + prf[v] - p.first];
            }
            for (pair<int, int> p:cnt2[id[i]]) {
                ans += (long long) p.second * cnt[id[v]][prf[par[v]] + prf[v] - p.first];
            }
            for (pair<int, int> p:cnt[id[i]]) {
                if (p.first >= prf[v]) cnt[id[v]][p.first] += p.second;
            }
            for (pair<int, int> p:cnt2[id[i]]) {
                if (p.first <= prf[v]) cnt2[id[v]][p.first] += p.second;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        char c; cin >> c; a[i] = c == '(' ? 1 : -1;
    }
    for (int i = 1; i < N; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= N; i++) {
        id[i] = i;
    }
    dfs2(1, 0);
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 42708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 114124 KB Output is correct
2 Correct 182 ms 119712 KB Output is correct
3 Correct 153 ms 114208 KB Output is correct
4 Correct 185 ms 118324 KB Output is correct
5 Correct 158 ms 114240 KB Output is correct
6 Correct 170 ms 116164 KB Output is correct
7 Correct 152 ms 114356 KB Output is correct
8 Correct 181 ms 116144 KB Output is correct
9 Correct 176 ms 114224 KB Output is correct
10 Correct 191 ms 121120 KB Output is correct
11 Correct 137 ms 114200 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 42708 KB Output isn't correct
2 Halted 0 ms 0 KB -