oj.uz

Submission #210098

# Submission time Handle Problem Language Result Execution time Memory
210098 2020-03-16T14:31:50 Z brcode Zagrade (COI17_zagrade) C++14
10 / 100
 2169 ms 58456 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
int sz[MAXN];
int ans;
int n;
vector<int> v1[MAXN];
bool blocked[MAXN];
int currsz;
map<int,int> m1;
map<int,int> m2;
map<int,int> ansm1;
map<int,int> ansm2;
string s;
void dfs(int curr,int par){
    currsz++;
    sz[curr] = 1;
    for(int x:v1[curr]){
        if(x!=par && !blocked[x]){
            dfs(x,curr);
            sz[curr]+=sz[x];
        }
    }
}
int findcentroid(int curr,int par){
    for(int x:v1[curr]){
        if(blocked[x]||x==par){
            continue;
        }
        if(sz[x]>currsz/2){
            return findcentroid(x,curr);
        }
    }
    return curr;
}
void dfsans(int curr,int par,int min1,int curr1,int min2,int curr2){
  //  cout<<curr1<<endl;
    if(blocked[curr]){
        return;
    }
    if(s[curr] == '('){
        if(min1 == 0){
            m1[curr1]++;
        }
    }else{
        if(min2 == curr2){
            m2[-curr2]++;
        }
    }
    for(int x:v1[curr]){
        if(x==par||blocked[curr]){
            continue;
        }
        if(s[x] == '('){
            dfsans(x,curr,min(0,min1+1),curr1+1,min2,curr2+1);
        }else{
            dfsans(x,curr,min(-1,min1-1),curr1-1,min(min2,curr2-1),curr2-1);
        }
    }
}
void solve(int curr){
    ansm1.clear();
    ansm2.clear();
    ansm1[0]++;
    ansm2[0]++;
   
    for(int x:v1[curr]){
        if(blocked[x]){
            continue;
        }
      
        m1.clear();
        m2.clear();
        if(s[x] == '('){
            dfsans(x,curr,0,1,0,1);
        }else{
            dfsans(x,curr,-1,-1,-1,-1);
        }
        //cout<<s[x]<<endl;
        
        if(s[curr]=='('){
           
            for(auto y:m1){
                
                ans+=1LL*m1[y.first]*ansm2[y.first+1];
            }
            for(auto y:m2){
                ans+=1LL*m2[y.first]*ansm1[y.first-1];
            }
        }else{
           
            for(auto y:m1){
               
                ans+=1LL*m1[y.first]*ansm2[y.first-1];
            }
            for(auto y:m2){
               // cout<<y.first<<endl;
                ans+=1LL*m2[y.first]*ansm1[y.first+1];
            }
        }
        for(auto y:m1){
            ansm1[y.first]+=y.second;
        }
        for(auto y:m2){
            ansm2[y.first]+=y.second;
        }
    }
}
void decompose(int curr,int par){
    currsz = 0;
    dfs(curr,curr);
    int cent = findcentroid(curr,curr);
   
    solve(cent);
   //cout<<cent<<" "<<ans<<endl;
    blocked[cent] = true;
    
    for(int x:v1[cent]){
        //cout<<x<<endl;
        if(!blocked[x]){
            //cout<<x<<endl;
            decompose(x,cent);
        }
    }
    blocked[cent] = false;
}
int main(){
    cin>>n;
    
    cin>>s;
    s='#'+s;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        v1[u].push_back(v);
        v1[v].push_back(u);
        //cout<<u<<" "<<v<<endl;
    }
    decompose(1,1);
    cout<<ans<<endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 37424 KB Output is correct
2 Correct 1305 ms 45676 KB Output is correct
3 Correct 772 ms 37480 KB Output is correct
4 Correct 1171 ms 43652 KB Output is correct
5 Correct 767 ms 37480 KB Output is correct
6 Correct 931 ms 40292 KB Output is correct
7 Correct 778 ms 37336 KB Output is correct
8 Correct 932 ms 40428 KB Output is correct
9 Correct 767 ms 37356 KB Output is correct
10 Correct 2169 ms 58456 KB Output is correct
11 Incorrect 608 ms 37352 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7420 KB Output is correct
2 Correct 11 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 12 ms 7420 KB Output is correct
6 Correct 10 ms 7448 KB Output is correct
7 Correct 11 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct
11 Correct 772 ms 37424 KB Output is correct
12 Correct 1305 ms 45676 KB Output is correct
13 Correct 772 ms 37480 KB Output is correct
14 Correct 1171 ms 43652 KB Output is correct
15 Correct 767 ms 37480 KB Output is correct
16 Correct 931 ms 40292 KB Output is correct
17 Correct 778 ms 37336 KB Output is correct
18 Correct 932 ms 40428 KB Output is correct
19 Correct 767 ms 37356 KB Output is correct
20 Correct 2169 ms 58456 KB Output is correct
21 Incorrect 608 ms 37352 KB Output isn't correct