Submission #210095

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
210095	2020-03-16T14:30:30 Z	brcode	Zagrade (COI17_zagrade)	C++14	Compilation error	0 ms	0 KB

zagrade

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 3e5+5;
long long sz[MAXN];
long long ans;
long long n;
vector<long long> v1[MAXN];
bool blocked[MAXN];
long long currsz;
map<long long,long long> m1;
map<long long,long long> m2;
map<long long,long long> ansm1;
map<long long,long long> ansm2;
string s;
void dfs(long long curr,long long par){
    currsz++;
    sz[curr] = 1;
    for(long long x:v1[curr]){
        if(x!=par && !blocked[x]){
            dfs(x,curr);
            sz[curr]+=sz[x];
        }
    }
}
long long findcentroid(long long curr,long long par){
    for(long long x:v1[curr]){
        if(blocked[x]||x==par){
            continue;
        }
        if(sz[x]>currsz/2){
            return findcentroid(x,curr);
        }
    }
    return curr;
}
void dfsans(long long curr,long long par,long long min1,long long curr1,long long min2,long long curr2){
  //  cout<<curr1<<endl;
    if(blocked[curr]){
        return;
    }
    if(s[curr] == '('){
        if(min1 == 0){
            m1[curr1]++;
        }
    }else{
        if(min2 == curr2){
            m2[-curr2]++;
        }
    }
    for(long long 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(long long curr){
    ansm1.clear();
    ansm2.clear();
    ansm1[0]++;
    ansm2[0]++;
   
    for(long long 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(long long curr,long long par){
    currsz = 0;
    dfs(curr,curr);
    long long cent = findcentroid(curr,curr);
   
    solve(cent);
   //cout<<cent<<" "<<ans<<endl;
    blocked[cent] = true;
    
    for(long long 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(long long i=1;i<n;i++){
        long long 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;
}

Compilation message

zagrade.cpp: In function 'void dfsans(long long int, long long int, long long int, long long int, long long int, long long int)':
zagrade.cpp:56:39: error: no matching function for call to 'min(int, long long int)'
             dfsans(x,curr,min(0,min1+1),curr1+1,min2,curr2+1);
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from zagrade.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
zagrade.cpp:56:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             dfsans(x,curr,min(0,min1+1),curr1+1,min2,curr2+1);
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from zagrade.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
zagrade.cpp:56:39: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             dfsans(x,curr,min(0,min1+1),curr1+1,min2,curr2+1);
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from zagrade.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
zagrade.cpp:56:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             dfsans(x,curr,min(0,min1+1),curr1+1,min2,curr2+1);
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from zagrade.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
zagrade.cpp:56:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             dfsans(x,curr,min(0,min1+1),curr1+1,min2,curr2+1);
                                       ^
zagrade.cpp:58:40: error: no matching function for call to 'min(int, long long int)'
             dfsans(x,curr,min(-1,min1-1),curr1-1,min(min2,curr2-1),curr2-1);
                                        ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from zagrade.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
zagrade.cpp:58:40: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             dfsans(x,curr,min(-1,min1-1),curr1-1,min(min2,curr2-1),curr2-1);
                                        ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from zagrade.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
zagrade.cpp:58:40: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
             dfsans(x,curr,min(-1,min1-1),curr1-1,min(min2,curr2-1),curr2-1);
                                        ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from zagrade.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
zagrade.cpp:58:40: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             dfsans(x,curr,min(-1,min1-1),curr1-1,min(min2,curr2-1),curr2-1);
                                        ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from zagrade.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
zagrade.cpp:58:40: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
             dfsans(x,curr,min(-1,min1-1),curr1-1,min(min2,curr2-1),curr2-1);
                                        ^