Submission #680638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
680638	2023-01-11T11:55:59 Z	nutella	Cats or Dogs (JOI18_catdog)	C++17	Compilation error	0 ms	0 KB

catdog

#include <bits/stdc++.h>
#include "catdog.h"

using namespace std;

int n;

constexpr int N = 100001;

vector<int> g[N];

int head[N], sz[N], parent[N], tin[N], T = 0, hld_sz[N], type[N];

int ans = 0;

array<int, 3> sum[N];

void dfs_init(int v) {
    auto it = find(g[v].begin(), g[v].end(), parent[v]);
    if (it != g[v].end()) {
        g[v].erase(it);
    }

    sz[v] = 1;
    for (int &to: g[v]) {
        parent[to] = v;
        dfs_init(to);
        sz[v] += sz[to];
        if (sz[to] > sz[g[v][0]]) {
            swap(to, g[v][0]);
        }
    }
}

void dfs_hld(int v) {
    if (head[v] == 0) {
        head[v] = v;
    }
    hld_sz[head[v]] += 1;
    tin[v] = T++;
    for (int &to: g[v]) {
        if (to == g[v][0]) {
            head[to] = head[v];
        }
        dfs_hld(to);
    }
}

struct Info {
    int dp[4]{};

    Info() = default;

    Info(int d[4]) {
        memcpy(dp, d, sizeof(dp));
    }
};

Info operator+(Info &a, Info &b) {
    Info res;
    memset(res.dp, 0x3f, sizeof(res.dp));
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            res.dp[]
        }
    }
}

struct SegmentTree {
    vector<Info> t;
    int n{};

    void init(int m) {
        n = 1 << (__lg(m) + bool(m & (m - 1)));
        t.assign(2 * n, {});
    }

    void modify(int i, Info x) {
        for (t[i += n] = x; i >>= 1;) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    array<int, 3> ans() {
        array<int, 3> ans{};
        for (int i = 0; i < 3; ++i) {
            ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
        }
        int mn = min({ans[0], ans[1], ans[2]});
        for (int i = 0; i < 3; ++i) {
            ans[i] = min(ans[i], mn + 1);
        }
        return ans;
    }

    int best() {
        int ans = numeric_limits<int>::max();
        for (int i = 0; i < 3; ++i) {
            ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
        }
        return ans;
    }
};

SegmentTree t[N];

void update(int v) {
    while (true) {
        int p = head[v];
        if (p != 1) {
            auto kek = t[p].ans();
            for (int i = 0; i < 3; ++i) {
                sum[parent[p]][i] -= kek[i];
            }
        }
        array<int, 3> now{};
        if (type[v] == 2) {
            now = sum[v];
        } else {
            now[0] = now[1] = now[2] = 0x3f3f3f3f;
            now[type[v]] = sum[v][type[v]];
        }
        t[head[v]].modify(tin[v] - tin[head[v]], now);
        if (p != 1) {
            auto kek = t[p].ans();
            for (int i = 0; i < 3; ++i) {
                sum[parent[p]][i] += kek[i];
            }
            v = parent[p];
        } else {
            break;
        }
    }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;

    for (int i = 0; i < n - 1; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }

    dfs_init(1);
    dfs_hld(1);

    for (int i = 1; i <= n; ++i) {
        if (head[i] == i) {
            t[i].init(hld_sz[i]);
        }
    }
}

int cat(int v) {
    type[v] = 0;

    update(v);

    return t[1].best();
}

int dog(int v) {
    type[v] = 1;

    update(v);

    return t[1].best();
}

int neighbor(int v) {
    type[v] = 2;

    update(v);

    return t[1].best();
}

Compilation message

catdog.cpp: In function 'Info operator+(Info&, Info&)':
catdog.cpp:64:20: error: expected primary-expression before ']' token
   64 |             res.dp[]
      |                    ^
catdog.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
   67 | }
      | ^
catdog.cpp: In member function 'std::array<int, 3> SegmentTree::ans()':
catdog.cpp:87:37: error: invalid types 'int[int]' for array subscript
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                     ^
catdog.cpp:87:52: error: invalid types 'int[int]' for array subscript
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                    ^
catdog.cpp:87:67: error: invalid types 'int[int]' for array subscript
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                   ^
catdog.cpp:87:77: error: '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'struct Info'} has no member named 'dq'; did you mean 'dp'?
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                             ^~
      |                                                                             dp
catdog.cpp:87:83: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                                   ^
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 catdog.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:
catdog.cpp:87:83: note:   candidate expects 2 arguments, 1 provided
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                                   ^
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 catdog.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:
catdog.cpp:87:83: note:   candidate expects 3 arguments, 1 provided
   87 |             ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from catdog.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:
/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:
catdog.cpp: In member function 'int SegmentTree::best()':
catdog.cpp:99:39: error: invalid types 'int[int]' for array subscript
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                       ^
catdog.cpp:99:54: error: invalid types 'int[int]' for array subscript
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                      ^
catdog.cpp:99:69: error: invalid types 'int[int]' for array subscript
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                     ^
catdog.cpp:99:79: error: '__gnu_cxx::__alloc_traits<std::allocator<Info>, Info>::value_type' {aka 'struct Info'} has no member named 'dq'; did you mean 'dp'?
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                               ^~
      |                                                                               dp
catdog.cpp:99:85: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                                     ^
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 catdog.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:
catdog.cpp:99:85: note:   candidate expects 2 arguments, 1 provided
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                                     ^
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 catdog.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:
catdog.cpp:99:85: note:   candidate expects 3 arguments, 1 provided
   99 |             ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
      |                                                                                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from catdog.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:
/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:
catdog.cpp: In function 'void update(int)':
catdog.cpp:123:50: error: cannot convert 'std::array<int, 3>' to 'Info'
  123 |         t[head[v]].modify(tin[v] - tin[head[v]], now);
      |                                                  ^~~
      |                                                  |
      |                                                  std::array<int, 3>
catdog.cpp:78:29: note:   initializing argument 2 of 'void SegmentTree::modify(int, Info)'
   78 |     void modify(int i, Info x) {
      |                        ~~~~~^