oj.uz

Submission #785158

# Submission time Handle Problem Language Result Execution time Memory
785158 2023-07-17T06:23:00 Z 이성호(#10023) Zagrade (COI17_zagrade) C++17
100 / 100
 367 ms 125440 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[par[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[par[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]]];
    if (a[v] == 1) cnt[id[v]][prf[v]]++;
    else 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[par[v]]) cnt[id[v]][p.first] += p.second;
            }
            for (pair<int, int> p:cnt2[id[i]]) {
                if (p.first <= prf[par[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);
    dfs2(1, 0);
    cout << ans << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42692 KB Output is correct
2 Correct 24 ms 42748 KB Output is correct
3 Correct 27 ms 42744 KB Output is correct
4 Correct 22 ms 42724 KB Output is correct
5 Correct 23 ms 42664 KB Output is correct
6 Correct 23 ms 42652 KB Output is correct
7 Correct 24 ms 42708 KB Output is correct
8 Correct 23 ms 42636 KB Output is correct
9 Correct 23 ms 42708 KB Output is correct
10 Correct 26 ms 42688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 118324 KB Output is correct
2 Correct 173 ms 123964 KB Output is correct
3 Correct 157 ms 118428 KB Output is correct
4 Correct 183 ms 122564 KB Output is correct
5 Correct 162 ms 118560 KB Output is correct
6 Correct 187 ms 120316 KB Output is correct
7 Correct 162 ms 118424 KB Output is correct
8 Correct 198 ms 120264 KB Output is correct
9 Correct 154 ms 118372 KB Output is correct
10 Correct 210 ms 125440 KB Output is correct
11 Correct 154 ms 118288 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42692 KB Output is correct
2 Correct 24 ms 42748 KB Output is correct
3 Correct 27 ms 42744 KB Output is correct
4 Correct 22 ms 42724 KB Output is correct
5 Correct 23 ms 42664 KB Output is correct
6 Correct 23 ms 42652 KB Output is correct
7 Correct 24 ms 42708 KB Output is correct
8 Correct 23 ms 42636 KB Output is correct
9 Correct 23 ms 42708 KB Output is correct
10 Correct 26 ms 42688 KB Output is correct
11 Correct 166 ms 118324 KB Output is correct
12 Correct 173 ms 123964 KB Output is correct
13 Correct 157 ms 118428 KB Output is correct
14 Correct 183 ms 122564 KB Output is correct
15 Correct 162 ms 118560 KB Output is correct
16 Correct 187 ms 120316 KB Output is correct
17 Correct 162 ms 118424 KB Output is correct
18 Correct 198 ms 120264 KB Output is correct
19 Correct 154 ms 118372 KB Output is correct
20 Correct 210 ms 125440 KB Output is correct
21 Correct 154 ms 118288 KB Output is correct
22 Correct 339 ms 83124 KB Output is correct
23 Correct 356 ms 83768 KB Output is correct
24 Correct 366 ms 83672 KB Output is correct
25 Correct 367 ms 83900 KB Output is correct
26 Correct 165 ms 93384 KB Output is correct
27 Correct 176 ms 87876 KB Output is correct
28 Correct 195 ms 85516 KB Output is correct
29 Correct 192 ms 125392 KB Output is correct
30 Correct 193 ms 125424 KB Output is correct
31 Correct 96 ms 77120 KB Output is correct
32 Correct 145 ms 118376 KB Output is correct