Submission #894984

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894984	2023-12-29T10:17:40 Z	vjudge1	Zagrade (COI17_zagrade)	C++17	Compilation error	0 ms	0 KB

zagrade

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 3e5 + 2;
const int M = 7e6 + 1;
int mod0 = 1e9+7, mod1 = 1e9+9;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 31;

int mult(int a, int b, int mod) {
    return a * 1LL * b % mod;
}

int sum(int a, int b, int mod) {
    a %= mod; 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n, int mod) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1, mod) * a % mod;
    } else {
        ll b = binpow(a, n / 2, mod);
        return b * b % mod;
    }
}

vector<int> g[N], ng[N];
int pc[N], used[N], sz[N], d[N];

void recalcsz(int v, int p){
    sz[v] = 1;
    for(auto u : g[v]){
        if(u != p && !used[u]){
            recalcsz(u, v);
            sz[v] += sz[u];
        }
    }
}

int getcentroid(int v, int p, int wh){
    for(auto u : g[v]){
        if(u != p && !used[u] && sz[u] > (wh / 2))
            return getcentroid(u, v, wh);
    }
    return v;
}

void decompose(int v, int p, int dp = 1){
    pc[v] = p;
    used[v] = 1;
    d[v] = dp;
    for(auto u : g[v]){
        if(!used[u]){
            recalcsz(u, -1);
            int c = getcentroid(u, -1, sz[u]);
            decompose(c, v, dp + 1);
        }
    }
}

gp_hash_table<int, pii> mp[N], mp1[N];
string s = "";

ll ans;
vector<int> dfs1(int v){
    vector<int> vs[sz(ng[v])];
    unordered_map<int, int> mpp;
    vector<int> ret = {v};
    for(int i = 0; i < sz(ng[v]); i++){
        vs[i] = dfs1(ng[v][i]);
        for(auto u : vs[i]){
            ret.pb(u);
            if(mp[u][v].S >= 0){
                if(s[v] == ')' && mp[u][v].F == 1)
                    ans++;
                ans += (ll)mpp[-mp[u][v].F];
            }
        }
        for(auto u : vs[i]){
            if(mp1[v][u].S >= mp1[v][u].F){
                mpp[mp1[v][u].F]++;
                if(mp1[v][u].F == 0)
                    ans++;
            }
        }
    }

    mpp.clear();
    for(int i = sz(ng[v]) - 1; i >= 0; i--){
        for(auto u : vs[i]){
            if(mp[u][v].S >= 0){
                ans += (ll)mpp[-mp[u][v].F];
            }
        }
        for(auto u : vs[i]){
            if(mp1[v][u].S >= mp1[v][u].F)
                mpp[mp1[v][u].F]++;
        }
    }
    return ret;
}

void nudela(int v, int p, int r, int c, int mn){
    if(s[v] == '(')
        c++;
    else
        c--;
    mn = min(mn, c);
    mp1[r][v] = {c, mn};
    for(auto u : g[v]){
        if(u != p && d[u] > d[r])
            nudela(u, v, r, c, mn);
    }
}

void neveroyatno(int v, int p, int r, int ver, int mn){
    if(v != r){
        if(s[v] == '(')
            mn = min(mn + 1, 0LL), ver++;
        else
            mn = min(mn - 1, -1LL), ver--;
        mp[v][r] = {ver, mn};
    }
    for(auto u : g[v]){
        if(d[u] > d[r] && u != p)
            neveroyatno(u, v, r, ver, mn);
    }
}

void solve(){
    int n;
    cin >> n;
    cin >> s;
    s = "@" + s;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    recalcsz(1, -1);
    int c = getcentroid(1, -1, sz[1]);
    decompose(c, -1);
    for(int i = 1; i <= n; i++)
        ng[pc[i]].pb(i);
    for(int i = 1; i <= n; i++)
        nudela(i, -1, i, 0, 0);
    for(int i = 1; i <= n; i++)
        neveroyatno(i, -1, i, 0, 0);
    /*for(int i = 1; i <= n; i++)
        cout << d[i] << ' ';
    //cout << '\n';
    for(auto e : mp){
        //cout << e.F.F << ' ' << e.F.S << ' ' << e.S.F << ' ' << e.S.S << '\n';
    }
    //cout << '\n';
    for(auto e : mp1){
        //cout << e.F.F << ' ' << e.F.S << ' ' << e.S.F << ' ' << e.S.S << '\n';
    }*/
    dfs1(c);
    cout << ans << '\n';
}   

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

zagrade.cpp: In function 'void neveroyatno(int, int, int, int, int)':
zagrade.cpp:147:33: error: no matching function for call to 'min(int, long long int)'
  147 |             mn = min(mn + 1, 0LL), ver++;
      |                                 ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
zagrade.cpp:147:33: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  147 |             mn = min(mn + 1, 0LL), ver++;
      |                                 ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
zagrade.cpp:147:33: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  147 |             mn = min(mn + 1, 0LL), ver++;
      |                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
zagrade.cpp:147:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  147 |             mn = min(mn + 1, 0LL), ver++;
      |                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
zagrade.cpp:147:33: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  147 |             mn = min(mn + 1, 0LL), ver++;
      |                                 ^
zagrade.cpp:149:34: error: no matching function for call to 'min(int, long long int)'
  149 |             mn = min(mn - 1, -1LL), ver--;
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
zagrade.cpp:149:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  149 |             mn = min(mn - 1, -1LL), ver--;
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
zagrade.cpp:149:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  149 |             mn = min(mn - 1, -1LL), ver--;
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
zagrade.cpp:149:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  149 |             mn = min(mn - 1, -1LL), ver--;
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from zagrade.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
zagrade.cpp:149:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  149 |             mn = min(mn - 1, -1LL), ver--;
      |                                  ^