oj.uz

Submission #207110

# Submission time Handle Problem Language Result Execution time Memory
207110 2020-03-06T13:58:43 Z Hideo Zagrade (COI17_zagrade) C++11
100 / 100
 671 ms 45928 KB 
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123

const int N = 3e5 + 7;
const int INF = 1e9 + 7;

pi st[N], fin[N];
int d[N], sub[N];
int n, t;
ll ans;
string s;

vi g[N];

void dfs (int v, int p = 0){
    sub[v] = 1;
    for (int to : g[v]){
        if (!d[to] && to != p){
            dfs(to, v);
            sub[v] += sub[to];
        }
    }
}

int fc (int v){
    bool good = true;
    int sz = sub[v] / 2, p = 0;
    while (good){
        good = false;
        for (int to : g[v]){
            if (!d[to] && to != p && sub[to] > sz){
                good = true;
                p = v; v = to;
                break;
            }
        }
    }
    return v;
}

vi nw;

void calc (int v, int p, int ad = 0, int bal = 0, int mnb = 0, int mxb = 0){
    if (s[v] == '(')
        bal++;
    else
        bal--;
    mxb = max(mxb, bal);
    mnb = min(mnb, bal);
    if (mxb == bal){
        if (bal){
            nw.pb(bal);
            if (mxb == bal){
                if (fin[bal + ad - (!ad)].sc != t)
                    fin[bal + ad - (!ad)] = {0, t};
                ans += fin[bal + ad - (!ad)].fr;
            }
        }
        else {
            nw.pb(INF);
            if (mxb == bal && ad){
                if (fin[bal + 1].sc != t)
                    fin[bal + 1] = {0, t};
                ans += fin[bal + 1].fr;
            }
        }
    }
    if (mnb == bal){
        if (bal){
            nw.pb(bal);
            if (mnb == bal){
                if (st[-bal + (!ad) - ad].sc != t)
                    st[-bal + (!ad) - ad] = {0, t};
                ans += st[-bal + (!ad) - ad].fr;
            }
        }
        else {
            nw.pb(-INF);
            if (mnb == bal && !ad){
                if (st[bal + 1].sc != t)
                    st[bal + 1] = {0, t};
                ans += st[bal + 1].fr;
            }
        }
    }
    for (int to : g[v])
        if (!d[to] && to != p)
            calc(to, v, ad, bal, mnb, mxb);
}

void cd (int v = 1){
    dfs(v);
    v = fc(v);
    fin[0] = {1, t};
    st[0] = {1, t};
    d[v] = 1;
    for (int to : g[v]){
        if (!d[to]){
            nw.clear();
            calc(to, v, (s[v] == '('));
            for (int it : nw){
                if (it == -INF){
                    if (fin[0].sc != t)
                        fin[0] = {0, t};
                    fin[0].fr++;
                }
                else if (it == INF){
                    if (st[0].sc != t)
                        st[0] = {0, t};
                    st[0].fr++;
                }
                else if (it < 0){
                    if (fin[-it].sc != t)
                        fin[-it] = {0, t};
                    fin[-it].fr++;
                }
                else {
                    if (st[it].sc != t)
                        st[it] = {0, t};
                    st[it].fr++;
                }
            }
        }
    }
    ++t;
    for (int to : g[v])
        if (!d[to])
            cd(to);
}

main(){
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 1; i < n; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].pb(b);
        g[b].pb(a);
    }
    cd();
    cout << ans;
}

Compilation message

zagrade.cpp:146:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
zagrade.cpp: In function 'int main()':
zagrade.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 10 ms 7420 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 38248 KB Output is correct
2 Correct 337 ms 43880 KB Output is correct
3 Correct 330 ms 42348 KB Output is correct
4 Correct 344 ms 43716 KB Output is correct
5 Correct 333 ms 42444 KB Output is correct
6 Correct 341 ms 42984 KB Output is correct
7 Correct 337 ms 42384 KB Output is correct
8 Correct 334 ms 42980 KB Output is correct
9 Correct 331 ms 42604 KB Output is correct
10 Correct 331 ms 45800 KB Output is correct
11 Correct 341 ms 43620 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 10 ms 7420 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 334 ms 38248 KB Output is correct
12 Correct 337 ms 43880 KB Output is correct
13 Correct 330 ms 42348 KB Output is correct
14 Correct 344 ms 43716 KB Output is correct
15 Correct 333 ms 42444 KB Output is correct
16 Correct 341 ms 42984 KB Output is correct
17 Correct 337 ms 42384 KB Output is correct
18 Correct 334 ms 42980 KB Output is correct
19 Correct 331 ms 42604 KB Output is correct
20 Correct 331 ms 45800 KB Output is correct
21 Correct 341 ms 43620 KB Output is correct
22 Correct 668 ms 24556 KB Output is correct
23 Correct 667 ms 24296 KB Output is correct
24 Correct 671 ms 24300 KB Output is correct
25 Correct 670 ms 24552 KB Output is correct
26 Correct 371 ms 29928 KB Output is correct
27 Correct 368 ms 27184 KB Output is correct
28 Correct 369 ms 26088 KB Output is correct
29 Correct 344 ms 45928 KB Output is correct
30 Correct 325 ms 45800 KB Output is correct
31 Correct 129 ms 24140 KB Output is correct
32 Correct 320 ms 43680 KB Output is correct