oj.uz

Submission #210093

# Submission time Handle Problem Language Result Execution time Memory
210093 2020-03-16T14:29:24 Z brcode Zagrade (COI17_zagrade) C++14
10 / 100
 2151 ms 62588 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+=m1[y.first]*ansm2[y.first+1];
            }
            for(auto y:m2){
                ans+=m2[y.first]*ansm1[y.first-1];
            }
        }else{
           
            for(auto y:m1){
               
                ans+=m1[y.first]*ansm2[y.first-1];
            }
            for(auto y:m2){
               // cout<<y.first<<endl;
                ans+=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 11 ms 7416 KB Output is correct
2 Correct 13 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 11 ms 7416 KB Output is correct
5 Correct 11 ms 7544 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7416 KB Output is correct
8 Correct 10 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 771 ms 41576 KB Output is correct
2 Correct 1317 ms 49896 KB Output is correct
3 Correct 770 ms 41684 KB Output is correct
4 Correct 1149 ms 47868 KB Output is correct
5 Correct 774 ms 41580 KB Output is correct
6 Correct 932 ms 44396 KB Output is correct
7 Correct 768 ms 41708 KB Output is correct
8 Correct 933 ms 44392 KB Output is correct
9 Correct 775 ms 41580 KB Output is correct
10 Correct 2151 ms 62588 KB Output is correct
11 Incorrect 618 ms 41480 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 13 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 11 ms 7416 KB Output is correct
5 Correct 11 ms 7544 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7416 KB Output is correct
8 Correct 10 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 771 ms 41576 KB Output is correct
12 Correct 1317 ms 49896 KB Output is correct
13 Correct 770 ms 41684 KB Output is correct
14 Correct 1149 ms 47868 KB Output is correct
15 Correct 774 ms 41580 KB Output is correct
16 Correct 932 ms 44396 KB Output is correct
17 Correct 768 ms 41708 KB Output is correct
18 Correct 933 ms 44392 KB Output is correct
19 Correct 775 ms 41580 KB Output is correct
20 Correct 2151 ms 62588 KB Output is correct
21 Incorrect 618 ms 41480 KB Output isn't correct