Submission #1189228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189228		patgra	Cat Exercise (JOI23_ho_t4)	C++20	Compilation error	0 ms	0 KiB

Main

#include <iostream>
#include <vector>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, tb, maxLog;
vector<int> perm;
vector<pair<int, int>> t;
vector<int> lz;
vector<vector<int>> g;
vector<int> depth, subsz, preord;
int pre_t;
ll ans, curAns;
vector<vector<int>> stMin;
vector<int> euDep, firstInEu;

void tAdd(int l, int r, int x) {
    DC << "   tAdd(" << l << ' ' << r << ' ' << x << ")" << eol;
    l += tb; r += tb;
    t[l].first += x;
    if(r != l) t[r].first += x;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) t[l + 1].first += x, lz[l + 1] += x;
        if(r % 2 == 1) t[r - 1].first += x, lz[r - 1] += x;
        l /= 2;
        r /= 2;
        t[l] = max(t[2 * l], t[2 * l + 1]);
        t[l].first += lz[l];
        t[r] = max(t[2 * r], t[2 * r + 1]);
        t[r].first += lz[r];
    }
    l /= 2;
    while(l) t[l] = max(t[2 * l], t[2 * l + 1]), t[l].first += lz[l], l /= 2;
}

void dfs(int v, int p) {
    depth[v] = depth[p] + 1;
    subsz[v] = 1;
    preord[v] = pre_t++;
    firstInEu[v] = (int)euDep.size();
    euDep.pb(depth[v]);
    repIn(u, g[v]) if(u != p) dfs(u, v), euDep.pb(depth[v]), subsz[v] += subsz[u];
}

int stMinQ(int l, int r) {
    if(l > r) swap(l, r);
    int k = 31 - __builtin_clz(r - l + 1);
    return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}

int dist(int a, int b) {
    auto ret = depth[a] + depth[b] - 2 * stMinQ(firstInEu[a], firstInEu[b]);
    DC << "  dist(" << a << ' ' << b << ") = " << ret << eol;
    return ret;
}

void reku(int v, int anc) {
    if(anc) curAns += dist(v, anc);
    DC << " ->  (" << v << ' ' << anc << ")  ans " << curAns << eol;
    ans = max(ans, curAns);
    repIn(u, g[v]) {
        if(depth[u] < depth[v]) {
            tAdd(preord[v], preord[v] + subsz[v] - 1, -1);
            if(t[1].first == 0) reku(t[1].second, v);
            tAdd(preord[v], preord[v] + subsz[v] - 1, 1);
        }
        else {
            tAdd(0, n - 1, -1);
            tAdd(preord[u], preord[u] + subsz[u] - 1, 1);
            if(t[1].first == 0) reku(t[1].second, v);
            tAdd(0, n - 1, 1);
            tAdd(preord[u], preord[u] + subsz[u] - 1, -1);
        }
    }
    if(anc) curAns -= dist(v, anc);
    DC << " <-  (" << v << ' ' << anc << ")" << eol;
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    perm.resize(n + 1);
    depth.resize(n + 1);
    subsz.resize(n + 1);
    preord.resize(n + 1);
    firstInEu.resize(n + 1);
    g.resize(n + 1);
    tb = 1 << (32 - __builtin_clz(n - 1));
    t.resize(2 * tb);
    lz.resize(2 * tb);
    rep(i, 0, n) cin >> perm[i + 1];
    rep(i, 1, n) {
        int a, b;
        cin >> a >> b;
        a = perm[a], b = perm[b];
        DC << a << ' ' << b << eol;
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(n, 0);
    rep(i, 1, n + 1) t[preord[i] + tb].second = i;
    rep(i, n, tb) t[i + tb].first = -1;
    repD(i, tb - 1, 0) t[i] = max(t[2 * i], t[2 * i + 1]);

    maxLog = 32 - __builtin_clz((int)euDep.size());
    stMin.resize(euDep.size(), vector<int>(maxLog, 1e9));
    rep(i, 0, (int)euDep.size()) stMin[i][0] = euDep[i];
    rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);

    reku(n, 0);
    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:122:96: error: no matching function for call to 'min(int, long long int)'
  122 |     rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);
      |                                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from Main.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
Main.cpp:122:96: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  122 |     rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);
      |                                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from Main.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
Main.cpp:122:96: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  122 |     rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);
      |                                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from Main.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
Main.cpp:122:96: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  122 |     rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);
      |                                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from Main.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
Main.cpp:122:96: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  122 |     rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1ll << (k - 1)))][k - 1]);
      |                                                                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~