oj.uz

Submission #334579

# Submission time Handle Problem Language Result Execution time Memory
334579 2020-12-09T12:57:01 Z Atill83 Zagrade (COI17_zagrade) C++14
100 / 100
 1339 ms 42616 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
string s;
vector<int> adj[MAXN];
bool erased[MAXN];
int sz[MAXN];
ll ans = 0;
int mp[MAXN];
void dfs(int v, int pr = -1){
    sz[v] = 1;
    for(int j: adj[v]){
        if(j != pr && !erased[j]){
            dfs(j, v);
            sz[v] += sz[j];
        }
    }
}

int cent(int v){
    int siz = sz[v];
    int pr = -1;
    bool cont = 1;
    while(cont){
        cont = 0;
        for(int j: adj[v]){
            if(erased[j] || j == pr) continue;
            if(2*sz[j] > siz){
                pr = v;
                v = j;
                cont = 1;
                break;
            }
        }
    }
    return v;

}

void upd(int v, int par, int val, int pre = 0, int tot = 0){
    if(s[v] == ')'){
        pre--;
        tot--;
    }else{
        pre++;
        tot = min(0, tot + 1);
    }

    //cerr<<v<<" "<<pre<<" "<<tot<<endl;
    if(tot == 0 && pre >= 0){
        mp[pre] += val;
    }

    for(int j: adj[v]){
        if(j != par && !erased[j]){
            upd(j, v, val, pre, tot);
        }
    }
}

void add(int v, int par, int pre = 0, int tot = 0){
    if(s[v] == ')'){
        pre++;
        tot = max(0, tot - 1);
    }else{
        pre--;
        tot++;
    }

    if(tot == 0 && pre >= 0){
        ans += mp[pre];
    }

    for(int j: adj[v]){
        if(!erased[j] && j != par){
            add(j, v, pre, tot);
        }
    }
}




void do_it(int v){
    dfs(v);
    v = cent(v);
    //cerr<<v<<endl;
    upd(v, -1, 1);
    ans += mp[0];
    int pr, tt;
    if(s[v] == ')')
        pr = tt = -1;
    else{
        pr = 1;
        tt = 0;
    }

    for(int j: adj[v]){
        if(erased[j])
            continue;
        upd(j, v, -1, pr, tt);
        add(j, v);
        upd(j, v, 1, pr, tt);
    }

    upd(v, -1, -1);


    erased[v] = 1;
    for(int j: adj[v])
        if(!erased[j])
            do_it(j);
}






int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;
    cin>>s;
    s = '.' + s;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    do_it(1);


    cout<<ans<<endl;

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 42160 KB Output is correct
2 Correct 535 ms 42004 KB Output is correct
3 Correct 571 ms 42072 KB Output is correct
4 Correct 556 ms 42172 KB Output is correct
5 Correct 569 ms 42200 KB Output is correct
6 Correct 566 ms 42276 KB Output is correct
7 Correct 580 ms 42200 KB Output is correct
8 Correct 576 ms 42164 KB Output is correct
9 Correct 567 ms 42064 KB Output is correct
10 Correct 456 ms 42584 KB Output is correct
11 Correct 468 ms 42200 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct
7 Correct 6 ms 7404 KB Output is correct
8 Correct 6 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 580 ms 42160 KB Output is correct
12 Correct 535 ms 42004 KB Output is correct
13 Correct 571 ms 42072 KB Output is correct
14 Correct 556 ms 42172 KB Output is correct
15 Correct 569 ms 42200 KB Output is correct
16 Correct 566 ms 42276 KB Output is correct
17 Correct 580 ms 42200 KB Output is correct
18 Correct 576 ms 42164 KB Output is correct
19 Correct 567 ms 42064 KB Output is correct
20 Correct 456 ms 42584 KB Output is correct
21 Correct 468 ms 42200 KB Output is correct
22 Correct 1317 ms 18904 KB Output is correct
23 Correct 1266 ms 18904 KB Output is correct
24 Correct 1297 ms 19032 KB Output is correct
25 Correct 1339 ms 18840 KB Output is correct
26 Correct 673 ms 26328 KB Output is correct
27 Correct 672 ms 22924 KB Output is correct
28 Correct 686 ms 21720 KB Output is correct
29 Correct 466 ms 42588 KB Output is correct
30 Correct 468 ms 42616 KB Output is correct
31 Correct 103 ms 19668 KB Output is correct
32 Correct 459 ms 42072 KB Output is correct