Submission #592425

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592425	2022-07-09T07:43:32 Z	Bobaa	Cats or Dogs (JOI18_catdog)	C++17	Compilation error	0 ms	0 KB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std; 

const int maxn = 1e5 + 5; 
int n;
vector<int> adj[maxn]; 
int A[maxn]; 
int sz[maxn]; 
int par[maxn]; 

void dfs_sz(int cur, int prv) {
	if (prv) adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv)); 
	sz[cur] = 1; 
	par[cur] = prv; 
	for (int nxt : adj[cur]) {
		dfs_sz(nxt, cur); 
		sz[cur] += sz[nxt]; 
	}
	nth_element(adj[cur].begin(), adj[cur].begin(), adj[cur].end(), [&](int i, int j) {
		return sz[i] > sz[j]; 
	}); 
}

int hvypar[maxn]; 
int num[maxn]; 
int pos[maxn]; 

void dfs_hld(int cur, int top) {
	hvypar[cur] = top; 
	pos[cur] = num[top]; 
	num[top]++; 
	bool isfrst = true; 
	for (int nxt : adj[cur]) {
		dfs_hld(nxt, (isfrst ? top : nxt)); 
		isfrst = false; 
	}
}

struct mat {
	int a00, a01, a10, a11; 
	friend math operator * (const mat& a, const mat& b) {
		mat r; 
		r.a00 = min(a.a00 + b.a00, a.a01 + b.a01); 
		r.a01 = min(a.a00 + b.a01, a.a01 + b.a11); 
		r.a10 = min(a.a10 + b.a00, a.a11 + b.a10); 
		r.a11 = min(a.a10 + b.a01, a.a11 + b.a11); 
		return r; 
	}
};

struct segtree {
	int s; 
	vector<mat> cost; 
	
	segtree() {}
	
	segtree(int n) {
		for (s = 1; s < n; s *= 2) {}
		cost = vector<mat>(2 * s); 
		for (int i = 0; i < 2 * s; i++) cost[i].a01 = cost[i].a10 = 1; 
	}
	
	void upd(int i, int& v0, int& v1) {
		i += s; 
		cost[i].a00 += v0; 
		cost[i].a01 += v0; 
		cost[i].a10 += v1; 
		cost[i].a11 += v1; 
		for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1]; 
	}
	
	void eval(int& a0, int& a1) {
		a0 = min(cost[1].a00, cost[1].a01); 
		a1 = min(cost[1].a10, cost[1].a11); 
	}
} seg[maxn]; 

void initialize(int k, vector<int> a, vector<int> b) {
	n = k; 
	for (int i = 0; i < n - 1; i++) {
		adj[a[i]].push_back(b[i]); 
		adj[b[i]].push_back(a[i]); 
	}
	for (int i = 1; i <= n; i++) A[i] = 0; 
	dfs_sz(1, 0); 
	dfs_hld(1, 1); 
	for (int i = 1; i <= n; i++) {
		assert((pos[i] == 0) == (hvypar[i] == i)); 
		if (hvypar[i] == i) seg[i] = segtree(num[i]); 
	}
}

int qry() {
	int a0, a1; 
	seg[1].eval(a0, a1); 
	return min(a0, a1); 
}

int cat(int v) {
	A[v] = 1; 
	upd(v, 0, n); 
	return qry(); 
}

int dog(int v) {
	A[v] = 2; 
	upd(v, n, 0); 
	return qry(); 
}

int neighbor(int v) {
	if (A[v] == 1) upd(v, 0, -n); 
	else if (A[v] == 2) upd(v, -n, 0); 
	else assert(false); 
	A[v] = 0; 
	return qry(); 
}

Compilation message

catdog.cpp:42:9: error: 'math' does not name a type; did you mean 'mat'?
   42 |  friend math operator * (const mat& a, const mat& b) {
      |         ^~~~
      |         mat
catdog.cpp: In member function 'void segtree::upd(int, int&, int&)':
catdog.cpp:70:49: error: no match for 'operator*' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} and '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'})
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from catdog.cpp:2:
/usr/include/c++/10/complex:391:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const std::complex<_Tp>&)'
  391 |     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:391:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::complex<_Tp>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from catdog.cpp:2:
/usr/include/c++/10/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const _Tp&)'
  400 |     operator*(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:400:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::complex<_Tp>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from catdog.cpp:2:
/usr/include/c++/10/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const std::complex<_Tp>&)'
  409 |     operator*(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:409:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::complex<_Tp>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::valarray<_Tp>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::valarray<_Tp>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from catdog.cpp:2:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
catdog.cpp:70:65: note:   '__gnu_cxx::__alloc_traits<std::allocator<mat>, mat>::value_type' {aka 'mat'} is not derived from 'const std::valarray<_Tp>'
   70 |   for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
      |                                                                 ^
catdog.cpp: In function 'int cat(int)':
catdog.cpp:102:2: error: 'upd' was not declared in this scope
  102 |  upd(v, 0, n);
      |  ^~~
catdog.cpp: In function 'int dog(int)':
catdog.cpp:108:2: error: 'upd' was not declared in this scope
  108 |  upd(v, n, 0);
      |  ^~~
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:113:17: error: 'upd' was not declared in this scope
  113 |  if (A[v] == 1) upd(v, 0, -n);
      |                 ^~~
catdog.cpp:114:22: error: 'upd' was not declared in this scope
  114 |  else if (A[v] == 2) upd(v, -n, 0);
      |                      ^~~