oj.uz

Submission #210100

# Submission time Handle Problem Language Result Execution time Memory
210100 2020-03-16T14:32:10 Z brcode Zagrade (COI17_zagrade) C++14
100 / 100
 2242 ms 62676 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
int sz[MAXN];
long long 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 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7420 KB Output is correct
8 Correct 11 ms 7420 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 37428 KB Output is correct
2 Correct 1317 ms 45716 KB Output is correct
3 Correct 789 ms 37472 KB Output is correct
4 Correct 1169 ms 43728 KB Output is correct
5 Correct 787 ms 37460 KB Output is correct
6 Correct 957 ms 40276 KB Output is correct
7 Correct 788 ms 37352 KB Output is correct
8 Correct 952 ms 40296 KB Output is correct
9 Correct 765 ms 37356 KB Output is correct
10 Correct 2242 ms 58384 KB Output is correct
11 Correct 592 ms 37352 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 10 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7420 KB Output is correct
8 Correct 11 ms 7420 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 10 ms 7416 KB Output is correct
11 Correct 770 ms 37428 KB Output is correct
12 Correct 1317 ms 45716 KB Output is correct
13 Correct 789 ms 37472 KB Output is correct
14 Correct 1169 ms 43728 KB Output is correct
15 Correct 787 ms 37460 KB Output is correct
16 Correct 957 ms 40276 KB Output is correct
17 Correct 788 ms 37352 KB Output is correct
18 Correct 952 ms 40296 KB Output is correct
19 Correct 765 ms 37356 KB Output is correct
20 Correct 2242 ms 58384 KB Output is correct
21 Correct 592 ms 37352 KB Output is correct
22 Correct 928 ms 22892 KB Output is correct
23 Correct 961 ms 22976 KB Output is correct
24 Correct 1014 ms 22936 KB Output is correct
25 Correct 1027 ms 22888 KB Output is correct
26 Correct 777 ms 29024 KB Output is correct
27 Correct 768 ms 26348 KB Output is correct
28 Correct 777 ms 25180 KB Output is correct
29 Correct 2216 ms 62676 KB Output is correct
30 Correct 2224 ms 62572 KB Output is correct
31 Correct 317 ms 22504 KB Output is correct
32 Correct 613 ms 41448 KB Output is correct