oj.uz

Submission #714852

# Submission time Handle Problem Language Result Execution time Memory
714852 2023-03-25T11:07:55 Z Ahmed57 Zagrade (COI17_zagrade) C++14
30 / 100
 467 ms 47148 KB 
#include <bits/stdc++.h>

using namespace std;
long long sz[300007];long long all = 0;
long long vis[300007];
vector<int> adj[300007];
bool ss = 0;
long long zz[300007];
string s;
long long bra = 0;
long long c = 0;
long long ch = 0;
void calc(int no,int pr){
    if(ss){
        if(s[no-1]=='('){bra++;ch--;ch=max(ch,0LL);}
        if(s[no-1]==')'){bra--;ch++;}
        if(bra>=0&&ch==0)zz[bra]++;
    }else{
        if(s[no-1]=='('){bra++;ch++;}
        if(s[no-1]==')'){bra--;ch--;ch=max(ch,0LL);}
        if(bra<=0&&ch==0){
            all+=zz[-bra];
            //cout<<no<<"pp"<<zz[-bra]<<"\n";
        }
        if(bra==0&&ch==0)c++;
    }
    for(auto i:adj[no]){
        if(i==pr||vis[i])continue;
        calc(i,no);
    }
}
int dfs(int no,int pr){
    sz[no] = 1;
    for(auto i:adj[no]){
        if(i==pr||vis[i]!=0)continue;
        sz[no]+=dfs(i,no);
    }
    return sz[no];
}
int get_centroid(int no,int ss,int pr){
    for(auto i:adj[no]){
        if(pr==i||vis[i]!=0)continue;
        if(sz[i]*2>ss){
            return get_centroid(i,ss,no);
        }
    }
    return no;
}
void centroid(int no){
    int cen = get_centroid(no,dfs(no,-1),-1);
    for(int i = 0;i<=sz[no]+5;i++){
        zz[i] = 0;
    }
    vector<int> v;
    vis[cen] = 1;
    c = 0;
    for(auto i:adj[cen]){
        if(vis[i])continue;
        v.push_back(i);
        ss = 0;
        ch = (s[cen-1]=='('?1:0);
        bra = (s[cen-1]=='('?1:-1);
        calc(i,-1);
        //cout<<all<<" "<<i<<endl;
        bra = 0;
        ch = 0;
        ss = 1;
        calc(i,-1);
    }
    all+=c;
    if(s[cen-1]==')')all+=zz[1];
    for(int i = 0;i<=sz[no]+5;i++){
        zz[i] = 0;
    }
    for(int i = v.size()-1;i>=0;i--){
        ss = 0;
        bra = (s[cen-1]=='('?1:-1);
        ch =(s[cen-1]=='('?1:0);
        calc(v[i],-1);
        bra = 0;
        ch = 0;
        ss = 1;
        calc(v[i],-1);
    }
    //cout<<cen<<"hh"<<all<<endl;
    for(auto i:adj[cen]){
        if(vis[i])continue;
        centroid(i);
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n>>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);
    }
    centroid(1);
    cout<<all<<endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 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 467 ms 43092 KB Output is correct
2 Correct 408 ms 47064 KB Output is correct
3 Correct 447 ms 46964 KB Output is correct
4 Correct 420 ms 47044 KB Output is correct
5 Correct 434 ms 46992 KB Output is correct
6 Correct 421 ms 47072 KB Output is correct
7 Correct 426 ms 47028 KB Output is correct
8 Correct 431 ms 46984 KB Output is correct
9 Correct 439 ms 47148 KB Output is correct
10 Correct 342 ms 47104 KB Output is correct
11 Correct 332 ms 47072 KB Output is correct

Subtask #3
0 / 60.0

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