Submission #884059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
884059	2023-12-06T15:13:31 Z	vjudge1	Cats or Dogs (JOI18_catdog)	C++17	Compilation error	0 ms	0 KB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;


template<typename Node>
struct AINT {
    vector<Node> aint;
    int n;
    Node ID;
    void init(int _n, Node id) {
        ID = id;
        n = _n;
        aint.resize(n * 2 + 5, Node());

    }

    void upd(int p, Node x, int node, int cl, int cr) {
        if(p < cl || cr < p) return;
        if(cl == cr) { aint[node] = x; return; }
        int mid = cl + cr >> 1;
        push(node, (mid - cl + 1) * 2);
        upd(p, x, node + 1, cl, mid);
        upd(p, x, node + (mid - cl + 1) * 2, mid + 1, cr);
        aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
//        cerr << cl << ' ' << cr << " :: \t" << aint[node].mat[0][0] << ' ' << aint[node].mat[1][1] << '\n'
    }
    Node query(int l, int r, int node, int cl, int cr) {
        if(r < cl || cr < l) return ID;
        if(l <= cl && cr <= r) return aint[node];
        int mid = cl + cr >> 1;
        push(node, (mid - cl + 1) * 2);
        return query(l, r, node + 1, cl, mid) + query(l, r, node + (mid - cl + 1) * 2, mid + 1, cr);
    }

    void upd(int p, Node x) { upd(p, x, 1, 1, n); }
    Node query(int l, int r) { return query(l, r, 1, 1, n); }


    void push(int node, int L) {;}
};

const int nmax = 1e5 + 5;
const int inf = 1e6 + 5;

namespace Tree {
    vector<int> g[nmax];

    int area[nmax];
    int pch[nmax], lastpoz[nmax], p[nmax];
    int pin[nmax], pout[nmax], inp = 1;

    int nodepoz(int node) { return pin[node];}

    namespace Init {
        void preinit(int node, int f) {
            p[node] = f;
            area[node] = 1;
            for(auto x : g[node]) {
                if(x == f) continue;
                preinit(x, node);
                area[node] += area[x];
            }
            return;
        }

        void init(int node, int f) {
            lastpoz[pch[node]] = inp;
            pin[node] = inp++;
            int mx = -1;
            for(auto x : g[node]) {
                if(x == f) continue;
                mx = mx == -1 || area[mx] < area[x]? x : mx;
            }
            if(mx == -1) {pout[node] = inp - 1; return; }
            pch[mx] = pch[node];
            init(mx, node);

            for(auto x : g[node]) {
               if(x == f || x == mx) continue;
               pch[x] = x;
               init(x, node);
            }
        }
    }

    struct Mat {
        int mat[2][2];
        Mat() { for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) mat[i][j] = inf; }
        Mat operator +(const Mat& x) const {
            Mat rez;

            for(int L = 0; L < 2; L++) {
                for(int M1 = 0; M1 < 2; M1++) {
                        for(int R = 0; R < 2; R++) {
                            rez.mat[L][R] = min(rez.mat[L][R], mat[L][M1] + min(x.mat[M1][R], x.mat[M1 ^ 1][R]));
                        }
                    }
                }
            }

            return rez;
        }
    };

    AINT<Mat> aint;

    struct SimpleDir {
        int red, blue;
        SimpleDir(int a = 0, int b = 0): red(a), blue(b) {;}
        SimpleDir operator +=(SimpleDir& x) { return *this = SimpleDir(red + min(x.red, x.blue + 1), blue + min(x.blue, x.red + 1)); }
        SimpleDir operator -=(SimpleDir& x) { return *this = SimpleDir(red - min(x.red, x.blue + 1), blue - min(x.blue, x.red + 1)); }
    };

    SimpleDir overson[nmax], mine[nmax];

    int color[nmax];

    Mat red(int node) {
        Mat curr;
        curr.mat[0][0] = overson[node].red;
        return curr;
    }

    Mat blue(int node) {
        Mat curr;
        curr.mat[1][1] = overson[node].blue;
        return curr;
    }

    Mat gol(int node) {
        Mat curr;
        curr.mat[0][0] = overson[node].red;
        curr.mat[1][1] = overson[node].blue;
        return curr;
    }

    void init(int node, int f) {
        aint.upd(nodepoz(node), gol(node));
        for(auto x : g[node])
            if(x != f)
                init(x, node);
        return;
    }

    void init(int n) {
        Mat ok;
        ok.mat[0][0] = 0;
        ok.mat[1][1] = 0;
        aint.init(n, ok);
        init(0, 0);
    }

    int upd(int node) {
        int father = pch[node];
        aint.upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));

        if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}

        overson[p[father]] -= mine[father];
        auto R = aint.query(pin[father], lastpoz[father]);
        mine[father] = SimpleDir(min(R.mat[0][0], R.mat[0][1]), min(R.mat[1][0], R.mat[1][1]));
        if(color[father] == 1) mine[father].blue = inf;
        if(color[father] == 2) mine[father].red = inf;

        overson[p[father]] += mine[father];

        return upd(p[node]);
    }
}

void initialize(int n, std::vector<int> A, std::vector<int> B) {
    for(int i = 0; i < n - 1; i++) {
        Tree::g[--A[i]].emplace_back(--B[i]);
        Tree::g[B[i]].emplace_back(A[i]);
    }

    Tree::Init::preinit(0, 0);
    Tree::pch[0];
    Tree::Init::init(0, 0);

    Tree::init(n);

    return;
}

int cat(int v) {
    Tree::color[--v] = 1;
  return Tree::upd(v);
}

int dog(int v) {
    Tree::color[--v] = 2;
  return Tree::upd(v);
}

int neighbor(int v) {
    Tree::color[--v] = 0;
  return Tree::upd(v);
}

Compilation message

catdog.cpp:104:13: error: expected unqualified-id before 'return'
  104 |             return rez;
      |             ^~~~~~
catdog.cpp:105:10: error: expected ';' after struct definition
  105 |         }
      |          ^
      |          ;
catdog.cpp: In member function 'Tree::Mat Tree::Mat::operator+(const Tree::Mat&) const':
catdog.cpp:102:13: warning: no return statement in function returning non-void [-Wreturn-type]
  102 |             }
      |             ^
catdog.cpp: At global scope:
catdog.cpp:108:10: error: 'Mat' was not declared in this scope; did you mean 'Tree::Mat'?
  108 |     AINT<Mat> aint;
      |          ^~~
      |          Tree::Mat
catdog.cpp:89:12: note: 'Tree::Mat' declared here
   89 |     struct Mat {
      |            ^~~
catdog.cpp:108:13: error: template argument 1 is invalid
  108 |     AINT<Mat> aint;
      |             ^
catdog.cpp:121:5: error: 'Mat' does not name a type; did you mean 'cat'?
  121 |     Mat red(int node) {
      |     ^~~
      |     cat
catdog.cpp:127:5: error: 'Mat' does not name a type; did you mean 'cat'?
  127 |     Mat blue(int node) {
      |     ^~~
      |     cat
catdog.cpp:133:5: error: 'Mat' does not name a type; did you mean 'cat'?
  133 |     Mat gol(int node) {
      |     ^~~
      |     cat
catdog.cpp: In function 'void init(int, int)':
catdog.cpp:141:14: error: request for member 'upd' in 'aint', which is of non-class type 'int'
  141 |         aint.upd(nodepoz(node), gol(node));
      |              ^~~
catdog.cpp:141:18: error: 'nodepoz' was not declared in this scope; did you mean 'Tree::nodepoz'?
  141 |         aint.upd(nodepoz(node), gol(node));
      |                  ^~~~~~~
      |                  Tree::nodepoz
catdog.cpp:55:9: note: 'Tree::nodepoz' declared here
   55 |     int nodepoz(int node) { return pin[node];}
      |         ^~~~~~~
catdog.cpp:141:33: error: 'gol' was not declared in this scope
  141 |         aint.upd(nodepoz(node), gol(node));
      |                                 ^~~
catdog.cpp:142:22: error: 'g' was not declared in this scope; did you mean 'Tree::g'?
  142 |         for(auto x : g[node])
      |                      ^
      |                      Tree::g
catdog.cpp:49:17: note: 'Tree::g' declared here
   49 |     vector<int> g[nmax];
      |                 ^
catdog.cpp: In function 'void init(int)':
catdog.cpp:149:9: error: 'Mat' was not declared in this scope; did you mean 'Tree::Mat'?
  149 |         Mat ok;
      |         ^~~
      |         Tree::Mat
catdog.cpp:89:12: note: 'Tree::Mat' declared here
   89 |     struct Mat {
      |            ^~~
catdog.cpp:150:9: error: 'ok' was not declared in this scope
  150 |         ok.mat[0][0] = 0;
      |         ^~
catdog.cpp:152:14: error: request for member 'init' in 'aint', which is of non-class type 'int'
  152 |         aint.init(n, ok);
      |              ^~~~
catdog.cpp: In function 'int upd(int)':
catdog.cpp:157:22: error: 'pch' was not declared in this scope; did you mean 'Tree::pch'?
  157 |         int father = pch[node];
      |                      ^~~
      |                      Tree::pch
catdog.cpp:52:9: note: 'Tree::pch' declared here
   52 |     int pch[nmax], lastpoz[nmax], p[nmax];
      |         ^~~
catdog.cpp:158:14: error: request for member 'upd' in 'aint', which is of non-class type 'int'
  158 |         aint.upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
      |              ^~~
catdog.cpp:158:18: error: 'nodepoz' was not declared in this scope; did you mean 'Tree::nodepoz'?
  158 |         aint.upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
      |                  ^~~~~~~
      |                  Tree::nodepoz
catdog.cpp:55:9: note: 'Tree::nodepoz' declared here
   55 |     int nodepoz(int node) { return pin[node];}
      |         ^~~~~~~
catdog.cpp:158:51: error: 'gol' was not declared in this scope
  158 |         aint.upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
      |                                                   ^~~
catdog.cpp:158:81: error: 'red' was not declared in this scope
  158 |         aint.upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
      |                                                                                 ^~~
catdog.cpp:158:93: error: 'blue' was not declared in this scope
  158 |         aint.upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
      |                                                                                             ^~~~
catdog.cpp:160:41: error: request for member 'query' in 'aint', which is of non-class type 'int'
  160 |         if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
      |                                         ^~~~~
catdog.cpp:160:47: error: 'pin' was not declared in this scope; did you mean 'Tree::pin'?
  160 |         if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
      |                                               ^~~
      |                                               Tree::pin
catdog.cpp:53:9: note: 'Tree::pin' declared here
   53 |     int pin[nmax], pout[nmax], inp = 1;
      |         ^~~
catdog.cpp:160:60: error: 'lastpoz' was not declared in this scope; did you mean 'Tree::lastpoz'?
  160 |         if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
      |                                                            ^~~~~~~
      |                                                            Tree::lastpoz
catdog.cpp:52:20: note: 'Tree::lastpoz' declared here
   52 |     int pch[nmax], lastpoz[nmax], p[nmax];
      |                    ^~~~~~~
catdog.cpp:160:138: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
  160 |         if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
      |                                                                                                                                          ^
In file included from /usr/include/c++/10/vector:60,
                 from catdog.h:3,
                 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:160:138: note:   candidate expects 2 arguments, 1 provided
  160 |         if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
      |                                                                                                                                          ^
In file included from /usr/include/c++/10/vector:60,
                 from catdog.h:3,
                 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:160:138: note:   candidate expects 3 arguments, 1 provided
  160 |         if(father == 0) { auto R = aint.query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
      |                                                                                                                                          ^
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:2:
/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:162:17: error: 'p' was not declared in this scope; did you mean 'Tree::p'?
  162 |         overson[p[father]] -= mine[father];
      |                 ^
      |                 Tree::p
catdog.cpp:52:35: note: 'Tree::p' declared here
   52 |     int pch[nmax], lastpoz[nmax], p[nmax];
      |                                   ^
catdog.cpp:163:23: error: request for member 'query' in 'aint', which is of non-class type 'int'
  163 |         auto R = aint.query(pin[father], lastpoz[father]);
      |                       ^~~~~
catdog.cpp:163:29: error: 'pin' was not declared in this scope; did you mean 'Tree::pin'?
  163 |         auto R = aint.query(pin[father], lastpoz[father]);
      |                             ^~~
      |                             Tree::pin
catdog.cpp:53:9: note: 'Tree::pin' declared here
   53 |     int pin[nmax], pout[nmax], inp = 1;
      |         ^~~
catdog.cpp:163:42: error: 'lastpoz' was not declared in this scope; did you mean 'Tree::lastpoz'?
  163 |         auto R = aint.query(pin[father], lastpoz[father]);
      |                                          ^~~~~~~
      |                                          Tree::lastpoz
catdog.cpp:52:20: note: 'Tree::lastpoz' declared here
   52 |     int pch[nmax], lastpoz[nmax], p[nmax];
      |                    ^~~~~~~
catdog.cpp: At global scope:
catdog.cpp:172:1: error: expected declaration before '}' token
  172 | }
      | ^
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:181:16: warning: statement has no effect [-Wunused-value]
  181 |     Tree::pch[0];
      |     ~~~~~~~~~~~^
catdog.cpp:184:11: error: 'init' is not a member of 'Tree'; did you mean 'Init'?
  184 |     Tree::init(n);
      |           ^~~~
      |           Init
catdog.cpp: In function 'int cat(int)':
catdog.cpp:190:11: error: 'color' is not a member of 'Tree'; did you mean 'color'?
  190 |     Tree::color[--v] = 1;
      |           ^~~~~
catdog.cpp:119:9: note: 'color' declared here
  119 |     int color[nmax];
      |         ^~~~~
catdog.cpp:191:16: error: 'upd' is not a member of 'Tree'; did you mean 'upd'?
  191 |   return Tree::upd(v);
      |                ^~~
catdog.cpp:156:9: note: 'upd' declared here
  156 |     int upd(int node) {
      |         ^~~
catdog.cpp: In function 'int dog(int)':
catdog.cpp:195:11: error: 'color' is not a member of 'Tree'; did you mean 'color'?
  195 |     Tree::color[--v] = 2;
      |           ^~~~~
catdog.cpp:119:9: note: 'color' declared here
  119 |     int color[nmax];
      |         ^~~~~
catdog.cpp:196:16: error: 'upd' is not a member of 'Tree'; did you mean 'upd'?
  196 |   return Tree::upd(v);
      |                ^~~
catdog.cpp:156:9: note: 'upd' declared here
  156 |     int upd(int node) {
      |         ^~~
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:200:11: error: 'color' is not a member of 'Tree'; did you mean 'color'?
  200 |     Tree::color[--v] = 0;
      |           ^~~~~
catdog.cpp:119:9: note: 'color' declared here
  119 |     int color[nmax];
      |         ^~~~~
catdog.cpp:201:16: error: 'upd' is not a member of 'Tree'; did you mean 'upd'?
  201 |   return Tree::upd(v);
      |                ^~~
catdog.cpp:156:9: note: 'upd' declared here
  156 |     int upd(int node) {
      |         ^~~